La génomique moléculaire fait face en ce début de siècle à de nouvelles situations qu'elle doit prendre en compte. D'une part, depuis une dizaine d'années, la quantité de données disponibles croît<br />de manière exponentielle. D'autre part, la recherche dans le domaine<br />implique de nouvelles questions dont les formulations in silico<br />génèrent des problèmes algorithmiquement difficiles à résoudre.<br /><br />Parmi ces problèmes, certains concernent notamment l'étude de réarrangements génomiques dont les duplications et les éléments transposables. Ils imposent que l'on soit en mesure de détecter précisément et efficacement de longues répétitions approchées et multiples dans les génomes. Par répétition multiple, nous désignons<br />des répétitions ayant au moins deux copies dans une séquence d'ADN, ou ayant des copies dans au moins deux séquences d'ADN distinctes. De plus, ces répétitions sont approchées dans le sens où des erreurs existent entre les copies d'une même répétition.<br /><br />La recherche de répétitions approchées multiples peut être résolue par des algorithmes d'alignements multiples locaux mais ceux-ci présentent une complexité exponentielle en la taille de l'entrée, et ne sont donc pas applicables à des données aussi grandes que des génomes. C'est pourquoi, de nouvelles techniques doivent être créées pour répondre à ces nouveaux besoins. <br /><br />Dans cette thèse, une approche de filtrage des séquences d'ADN est<br />proposée. Le but d'une telle approche est de supprimer rapidement et<br />efficacement, parmi des textes représentant des séquences d'ADN, de<br />larges portions ne pouvant pas faire partie de répétitions. Les données filtrées, limitées en majorité aux portions pertinentes, peuvent alors être fournies en entrée d'un algorithme d'alignement multiple local.<br /><br /><br />Les filtres proposés appliquent une condition nécessaire aux séquences pour n'en conserver que les portions qui la respectent. Les travaux que nous présentons ont porté sur la création de conditions de filtrage, à la fois efficaces et simples à appliquer d'un point de vue algorithmique. À partir de ces conditions de filtrage, deux filtres, Nimbus et Ed'Nimbus, ont été créés. Ces filtres sont appelés exacts car il ne suppriment jamais de données contenant effectivement des occurrences de répétitions respectant les caractéristiques fixées par un utilisateur. L'efficacité du point de vue de la simplicité d'application et de celui de la précision du filtrage obtenu, conduit à de très bons résultats en pratique. Par exemple, le temps utilisé par des algorithmiques de recherche de répétitions ou d'alignements multiples peut être réduit de plusieurs ordres de grandeur en utilisant les filtres proposés.<br /><br />Il est important de noter que les travaux présentés dans cette thèse<br />sont inspirés par une problématique biologique mais ils sont également généraux et peuvent donc être appliqués au filtrage de tout type de textes afin d'y détecter de grandes portions répétées.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00132300 |
| Date | 21 September 2006 |
| Creators | Peterlongo, Pierre |
| Publisher | Université de Marne la Vallée |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0027 seconds