Thesis of Yoann Dufresne

Algorithmique pour l'annotation automatique de Peptides Non Ribosomiques

La composition monomérique de polymères joue un rôle essentiel dans la comparaison de structures et dans la biologie de synthèse. Cependant, la plupart des ressources moléculaires en ligne donne accès à la structure atomique des molécules et non à leur structure monomérique. Nous avons donc créé un logiciel appelé smiles2monomers (s2m) pour inférer la structure monomérique passer des atomes aux monomères. L’algorithme sous-jacent se déroule en deux phases : une phase de recherche par isomorphisme de sous graphe des monomères au sein de la structure atomique puis une recherche du meilleur pavage non chevauchant des monomères trouvés. La recherche est basée sur un index markovien améliorant les vitesses de recherche de 30% par rapport à l’état de l’art. Le pavage est lui constitué d’un algorithme glouton couplé à un raffinement par “branch & cut”. s2m a été testé sur deux jeux de données déjà annotés. Il retrouve les annotations manuelles avec une excellente sensibilité en des temps très courts. Notre équipe développe Norine, base de données de référence de polymères particuliers appelés Peptides Non Ribosomiques (NRP). s2m, exécuté sur l’ensemble des données de Norine, a mis à jour de nombreuses annotations erronées en base. s2m est donc à la fois capable de créer de nouvelles annotations et d’en corriger des anciennes. Les nouvelles annotations nous servent à la fois à découvrir de nouveaux NRP, de nouvelles fonctionnalités NRP et potentiellement dans le futur à synthétiser des NRP non naturels.

Jury

Directeurs de thèse : Maude Pupin, Laurent Noé Rapporteurs : Marie-France Sagot, Frédérique Lisack Examinateurs : Pablo Carbonell, Dave Ritchie, Sophie Tison, François Boulier, Valérie Leclère

Thesis of the team Bonsai defended on 01/12/2016