Localisation à grande échelle de motifs nucléiques décrits par des matrices position-poids

Ce travail s'inscrit dans le cadre de la recherche de courts motifs nucléiques approchés modélisés par des matrices position-poids, qui décrivent le contenu informationnel d'un motif position par position. L'annotation des génomes fait émerger des nouveaux besoins de recherche de sites de fixation potentiels à grand échelle, que ce soit dans un but de génomique comparative ou d'extraction de sites sur-représentés pour des gènes co-régulés.
Les programmes usuels de localisation de matrices ne sont pas adaptés à ce type de travail. Nous présentons une première tentative d'accélération du calcul en présence d'une banque de matrices. L'idée est de tirer parti du fait que les banques de matrices sont des données stables, que l'on peut pré-traiter.

Algorithme exact L'algorithme que nous proposons repose essentiellement sur le pré-calcul des scores pour chaque motif dans une structure d'index. Au regard du nombre de colonnes des matrices (entre 9 et 30 bases
en pratique), il est nécessaire de recourir à un index modulaire, organisé en sous-tables, ce qui revient à découper chaque matrice en petites sous-matrices (c'est un problème d'optimisation qui se résout par programmation dynamique). Cette démarche exploite en fait la propriété d'additivité du score. De plus, une anticipation du résultat final à partir du résultat partiel se fait sur la base des scores minimaux et maximaux associés au résultat partiel restant.

Similitude entre matrices La seconde direction de recherche que nous avons explorée est liée à la similitude entre matrices, et donc à la similitude entre les sites reconnus associés. Les matrices ne sont pas toutes indépendantes, et certaines s'organisent naturellement en groupes homogènes, que ce soit pour des raisons biochimiques intrinsèques ou historiques. La motivation pour cette analyse est double: il s'agit à la fois de faire le tri parmi les prédictions en détectant les redondances dues à la proximité des matrices, et de chercher à exploiter cette redondance pour accéler éventuellement la localisation des sites.

Le problème de comparer des matrices a été abordé récemment, mais sans mener à la corrélation entre les
prédictions de sites de fixation. Nous montrons qu'il est possible, sous certaines hypothèses, de déterminer exactement la proportion de prédictions communes et de prédiction distinctes entre deux matrices. Cette analyse
permet également d'accélerer l'algorithme de localisation de la section précédente, en travaillant sur des groupes de matrices similaires. On obtient ainsi un algorithme approché, à grain plus ou moins fin suivant les taux maximums de faux positifs et faux négatifs tolérés.