Projet de programmation en Master 1 Informatique (année 2015/2016)   Recherche optimisée de palindromes communs dans des groupes de génomes bactériens   Présentation du projet Les biologistes utilisent des séquences d'ADN, stockées informatiquement sous forme de chaines de caractères au format FASTA à l'aide des 4 lettres A, T, G et C. Un palindrome non constant est une chaine de caractères qui peut se lire de la droite vers la gauche ou de la gauche vers la droite, comme ACA ou GATTAG. Il serait intéressant de détecter de tels palindromes et de disposer, pour des séquences d'ADN, d'indications de présence et de position des palindromes, soit individuels soit communs à une classe de séquences. On ne s'intéresse pas ici aux palindromes de 2, 3, 4... lettres mais aux plus grands palindromes présents dans les séquences. Détails du projet On viendra écrire en PHP un programme qui s'exécute en ligne de commandes pour effectuer ce type de recherche. Il y aura sans doute deux paramètres : le nom du fichier contenant les séquences Fasta, une indication du mode (global, par classe, individuel). Les résultats seront renvoyés au final dans un fichier-texte au format CSV, même si on pourra stocker des résultats partiels dans une base de données (format conseillé : sqlite3). On veillera à ce que le programme s'exécute rapidement. On pourra par exemple s'amuser à déterminer théoriquement la complexité ou le nombre de sous-chaines de caractères à explorer avec une version naive de recherche de palindrome. Il n'est pas sans doute pas indispensable de construire des classes d'objets PHP pour réaliser le projet et on pourra donc se contenter de fonctions. On respectera le style de codage de G. HUNAULT pour la syntaxe des fonctions PHP (voir par exemple std.php) et on essaiera de fournir des indications sur le profil d'exécution (temps passé dans chaque étape, chaque fonction importante). Données à traiter On trouvera sur la page 1055genomes.php des fichiers qui contiennent des séquences d'ADN bactériens. Ces fichiers serviront de jeux d'essais réels. Il est conseillé de commencer par construire des jeux d'essais beaucoup plus petits pour mettre au point les programmes. On essaiera dans un premier temps de fournir le plus grand palindrome de Pseudomonas putida GB-1 avant d'essayer de trouver le plus grand palindrome commun des 5 exemplaires de Pseudomonas putidaetc. Attention : ce projet demande de fortes compétences en algorithmique. En particulier, on pourra s'intéresser à la structure de données nommée arbre des suffixes. Code-source de la page.

 

 

   Retour à la page principale de   (gH)