Projet de programmation en Master 1 Informatique Année 2014-2015   Plus-grandes sous-séquences de caractères qui... 1. Présentation du sujet Les méthodes «récentes» en biologie utilisent principalement deux types de séquences : les séquences nucléotidiques (ADN) et les séquences protéiques (acides aminés), stockées informatiquement sous forme de chaines de caractères au format FASTA. Il existe dans la littérature informatique classique de nombreux algorithmes intéressants sur les chaines de caractères comme - la plus grande sous-chaine constante d'une chaine donnée, - la plus grande sous-chaine constante d'une chaine donnée avec un caractère fixé, - la plus grande sous-chaine répétée d'une chaine donnée... Une première généralisation consiste à remplacer sous-chaine par sous-séquence. Une deuxième généralisation consiste à remplacer sous-chaine d'une chaine donnée par sous-chaine commune d'un ensemble de chaines données. Et bien sûr la troisième généralisation consiste à remplacer sous-chaine d'une chaine donnée par sous-séquence commune d'un ensemble de chaines données. Le but du projet est de programmer ces calculs pour les deux types de séquences. 2. Détails concernant le projet La première partie du projet consiste à imaginer une bibliothèque de fonctions pour calculer ces différentes sous-chaines et sous-séquences en définissant rigoureusement les paramètres d'entrée et de sortie (par exemple pour la plus grande sous-chaine répétée, il faut aussi renvoyer le nombre de répétitions et la position des répétitions). On essaiera de trouver des noms simples et évocateurs pour les fonctions et on analysera la complexité des méthodes ou algorithmes sous-jacents sachant que  : les séquences protéiques sont en général assez courtes (de l'ordre de quelques centaines de caractères) alors que les séquences nucléotidiques sont en général plutôt longues (de l'ordre de quelques millions de caractères pour l'ADN bactérien, de plusieurs milliards de caractères pour l'ADN humain). les séquences nucléotidiques utilisent un alphabet de 4 lettres (A,C,G,T) alors que les séquences protéiques ont un alphabet de 20 lettres (lettres majuscules sauf BJOUXZ). il n'est sans doute pas possible de calculer la plus grande sous-séquence commune d'un ensemble de de séquences nucléotidiques données en un temps "raisonnable". La deuxième partie du projet viendra implémenter ces fonctions en PHP et évaluer la durée de leur exécution sur des séquences protéiques "bien connues", celles des classes de LEAPdb et celles de sHSPdb. La troisième partie du projet viendra implémenter ces fonctions en PERL et évaluer la durée de leur exécution (que l'on comparera à celle des fonctions PHP correspondantes) sur les séquences d'ADN bactérien décrites à la fin de la page 1055genomes.php. 3. Fichiers de données fournis Fichier Description LEAdb les 1422 séquences Fasta de protéines de LEAPdb (décembre 2014). sHSPdb les 4609 séquences Fasta de protéines de sHSPdb (décembre 2014). putidaGB1 un exemplaire du génome bactérien de Pseudomonas putida. putidas cinq génomes bactériens correspondant à Pseudomonas putida. Pour LEAPdb et sHSPdb, la fin de l'identifiant indique la classe. Ainsi 1YYCA_cl_7 indique que la chaine protéique 1YYCA est en classe 7. Remarque : Il faut donc essayer de programmer des fonctions rapides. Ce terme fait référence au temps de calcul (pas au temps d'affichage). On pourra par exemple consulter l'article de Vinga et al. (copie locale) et la page Web de mummer pour plus de détails sur ce sujet. On commencera donc par calculer des sous-chaines plutôt que des sous-séquences.

 

 

   Retour à la page principale de   (gH)