En biologie moléculaire, l'assemblage de fragments d'une séquence d'ADN est une opération fondamentale. En effet, les procédés de séquençage (identification de la séquence de bases A, C, G, T) actuels ne peuvent traiter des molécules complètes, qui ont typiquement entre 10000 et 100000 paires de bases (PBs). Ces procédés fournissent des fragments de quelques centaines de PBs, prélevés aléatoirement, qui correspondent à des facteurs de la séquence recherchée. On obtient typiquement 500 à 2000 de ces fragments, qui présentent entre eux de nombreux recouvrements.
Le problème de la plus courte sur-séquence commune (SSC) d'un ensemble de séquences est une idéalisation du problème de l'assemblage. Soit une collection F de mots sur l'alphabet {A,C,G,T}, il s'agit de trouver un mot S de longueur minimale tel que tout mot f de F soit un facteur de S. Par exemple, si F={TAG,CTA,ACT}, les mots TAGCTAACT, CTACTAG et ACTAG sont des sur-séquences communes de F, et le mot S=ACTAG est la plus courte sur-séquence commune de F.
On peut voir également ce problème comme un problème de compression, la solution est en effet une représentation compacte des données d'origine. Dans l'exemple ci-dessus, le taux de compression est de 5/9.
On supposera, sans perte de généralité, qu'aucun mot de F n'est lui-même un facteur d'un autre mot de F. En effet, si u est facteur d'un autre mot de F, alors une solution pour F - {u} est également une solution pour F.
Les recouvrements (overlaps) entre les mots de F jouent évidemment un rôle majeur dans la solution de ce problème. Proposer une structure de graphe pondéré pour représenter une collection F et les recouvrements entre les mots de F.
Dans ce graphe pondéré, comment s'exprime le problème de la recherche d'une plus courte SSC ? Connaissez-vous un problème apparenté ?
Proposer un algorithme glouton G pour trouver une ``courte'' SSC. Un tel algorithme a été proposé en 1980 par Gallant, Maier et Storer. Ils ont montré que le taux de compression obtenu par G est au plus le double du taux de compression optimal.
Donner un exemple où la solution donnée par cet algorithme n'est pas la solution optimale.
L'efficacité de G est liée à celle de l'opération élémentaire qui consiste à calculer la longueur maximale d'un recouvrement entre deux mots u et v. Proposer un algorithme linéaire pour réaliser cette opération. (Indication : on essaiera de se ramener à un problème connu.)
Ecrire un programme construisant le graphe des recouvrements à partir d'une collection de fragments.
Dans certains cas, on est ``presque sûr'' que les recouvrements pertinents sont de taille supérieure à un certain seuil t. On peut alors retirer du graphe des recouvrements les arcs de poids inférieur à t.
De plus, si la séquence à reconstruire ne comporte pas de facteur répété de taille supérieure ou égale à t, ni de fragments qui sont eux-mêmes facteurs d'autres fragments, on peut montrer qu'alors le graphe des recouvrements ainsi "filtré" est sans circuit.
Plus précisément :
Soit F = {fi}, i=0..N-1 une famille de mots sur A, soit
t un entier naturel,
La famille F est dite t-connectée si pour tout couple
fi, fj d'éléments de F, il
existe une séquence x0...xk de mots
de F telle que x0 = fi, xk =
fj, et pour tout i de 1 à k,
suffixe(xi-1, t') = prefixe(xi,
t') avec t' supérieur ou égal à t.
La famille F est dite sans sous-intervalle si pour tout mot
fi de F, fi n'est pas un facteur d'un autre
mot fj de F.
Théorème ("Introduction to Computational
Molecular Biology", J.C. Setubal, J. Meidanis, chap. 4, p. 129)
Soit X un mot sur A, soit F un échantillonnage (famille de facteurs)
sans sous-intervalle et t-connecté de X.
Si X ne contient pas de facteur répété de taille
supérieure ou égale à t, alors le graphe des recouvrements
de longueur supérieure ou égale à t est sans circuit.
Combien y-a-t-il, au plus, de chemins Hamiltoniens dans un graphe sans circuit ? Justifiez votre réponse.
Proposer un algorithme linéaire pour trouver un chemin Hamiltonien dans le graphe des recouvrements "filtré", ou indiquer qu'il n'en existe pas.
Implémenter et tester cet algorithme.
"Text Algorithms", M. Crochemore, W. Rytter, Oxford University Press, 1994
"Algorithms on Strings, Trees and Sequences", D. Gusfield, Cambridge University Press, 1997
"Introduction to Computational Molecular Biology", J.C. Setubal, J. Meidanis, PWS Publishing Company, 1997
"Introduction to Computational Biology", M. S. Waterman, Chapman Ed., 1995