Le devoir 2 : Alignement de grandes séquences biologiques
Table des matières
- 1 Présentation
- 2 Ce qu'il y a à faire
- 3 Le matériel
- 4 Mes résultats
- 5 Comment chercher une séquence d'ADN sur Internet?
- 6 Comment construire un "dotplot" ?
- 7 Quelques liens fort utiles
1 Présentation
1.1 Motivations du devoir
Il s'agit de programmer l'alignement de deux séquences et de l'appliquer à quelques exemples issus de la Biologie. Cette année je me suis intéressé à l'alignement de grandes séquences biologiques. On dispose maintenant des génomes complets de nombreuses espèces. Cela permet de deviner la fonction de certains gènes de nouvelles espèces en les comparant à des espèces mieux connues. On est donc amené à comparer les séquences de chromosomes complets (ou de grandes parties). Regarder par exemple l'article suivant :Alignment of Whole Genomes. A.L. Delcher, S. Kasif, R.D. Fleischmann, J. Peterson, O. White, and S.L. Salzberg. Nucleic Acids Research, 27:11 (1999), 2369-2376. (l'article pour ceux qui n'arriveraient pas à le télécharger l'article est ici)L'objectif de ce devoir est de faire un programme qui permet de comparer deux séquences d'ADN (celles qui sont décrites à la fin de l'article précédent : "human chromosome 12p13 and its syntenic region in mouse chromosome 6"). Plus précisement :
we chose a 222 930 bp subsequence of human chromosome 12p13 (accession no. U47924) that is syntenic to a 227 538 bp contiguous subsequence of mouse chromosome 6 (accession no. AC002397). These sequences were the subject of a recent study by AnsariLari et al. (PDF)ATTENTION : ces articles présentent une méthode qui n'est pas celle que nous allons utiliser
1.2 Description de l'objectif du devoir
Cela ne se fait pas simplement : l'algorithme classique construit autour de la programmation dynamique ne peut pas marcher dans de tels cas. En effet il utilise un capacité mémoire de l'ordre de O(n2) si n est la taille des chaînes à comparer. Dans le cas qui nous intéresse, n vaut environ 230000. Il faut donc une mémoire de 230000*230000*4 = 211600 Moctets = 211 Go. (c'est assez rare de trouver un ordinateur avec une telle capacité). Il faut donc changer d'algorithme. J'ai donc choisit d'utiliser un algorithme basé sur la méthode de Hirschberg qui utilise un espace mémoire en O(n) pour un temps de calcul un peu plus lent que l'algorithme classique.Une version plus élaborée de ce que je vous demande de programmer, se trouve dans un ensemble de programmes pour la biologie : EMBOSS. Il s'agit du programme stretcher. Voici l'article correspondant à ce programme : Eugene W. Myers, Webb Miller: Optimal alignments in linear space. Computer Applications in the Biosciences 4(1): 11-17 (1988) . La version PDF de cet article.
2 Ce qu'il y a à faire
Le vrai sujet du devoir- Programmer l'algorithme classique d'alignement global de séquence avec coût de gap constant à l'aide de la programmation dynamique.
- La même chose avec l'algorithme de Hirschberg.
- Testez vos deux méthodes avec de petits exemples. Utilisez la valeur de gap et la matrice de similarité donnée dans le paragraphe suivant.
- Comparez sur des exemples tirés au hasard, les performances en mémoire et en temps de ces deux méthodes. Le but est de vérifier que le temps de calcul n'est pas plus du double que dans la méthode classique et que la mémoire utilisée est effectivement linéaire.
- Traitez à titre de vérification le premier exemple (avec la méthode de Hirschberg) -- vous pouvez construire le dotplot
- Passez le deuxième exemple -- attention cela est très long (1h20 chez moi) -- vous pouvez construire le dotplot avec "dotter", mais c'est assez lent. Question subsidiaire : quelle est la plus longue sous-chaîne qui s'aligne sans aucun gap ?
- Rédigez 2 ou 3 pages sur l'algorithme de Hirschberg, ainsi que sur la démonstration des complexité en mémoire et en temps.
- Environ 1 ou 2 pages de résultats de test
- 1 tableau de comparaison des 2 méthodes
- Les résultats de la première question (je ne veux pas des pages et des pages d'alignement)
- Les résultats de la deuxième question (Même remarque)
- Conclusions et commentaires (est-ce que cela vous a intéressé?). Pouvez-vous proposer une méthode pour améliorer l'efficacité de l'algorithme.
Remarque2 : Je veux un document d'au plus une dizaine de pages avec des phrases en français. N'oubliez pas que c'est à vous de me prouver par des exemples que vôtre programme est juste. Je ne souhaite le listing que pour vérifier que vous n'avez pas copié!!
3 Le matériel
3.1 La description de l'algorithme classique
Je vous donne les Pages 52-53 du livre Introduction to Computational Molecular Biology (voir référence à la fin) qui décrivent le programme d'alignement. Voici mon programme en Java align.java qui fait la même chose (pour aider ceux qui n'y arrivent pas), mais ce programme est donné sans aucune garantie.3.2 La description de l'algorithme de Hirschberg
Il y a une très bonne description de cet algorithme dans le livre de Meidanis and Setubal Pages 58-61. Vous pouvez aussi consulter les transparents : Linear Alignment3.3 Le cout du gap et la matrice de similarité
J'ai choisit comme coût fixe du gap la valeur -8. La matrice est la suivante:
Matrice de similarité
| |
|
