Computational methods for de novo assembly of next-generation genome sequencing data

Rayan Chikhi 1
1 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Résumé : Dans cette thèse, nous présentons des méthodes de calcul (modèles théoriques et algorithmiques) pour effectuer la reconstruction de séquences d'ADN. Il s'agit de l'assemblage de novo de génome à partir de lectures (courte séquences ADN) produites par des séquenceurs à haut débit. Ce problème est difficile, aussi bien en théorie qu'en pratique. Du point de vue théorique, les génomes sont structurellement complexes. Chaque instance d'assemblage de novo doit faire face à des ambiguïtés de reconstruction. Les lectures peuvent conduire à un nombre exponentiel de reconstructions possibles, une seule étant correcte. Comme il est impossible de déterminer laquelle, une approximation fragmentée du génome est retournée. Du point de vue pratique, les séquenceurs produisent un énorme volume de lectures, avec une redondance élevée. Une puissance de calcul importante est nécessaire pour traiter ces lectures. Le séquençage ADN évolue désormais vers des génomes et méta-génomes de plus en plus grands. Ceci renforce la nécessité de méthodes efficaces pour l'assemblage de novo. Cette thèse présente de nouvelles contributions en informatique autour de l'assemblage de génomes. Ces contributions visent à incorporer plus d'information pour améliorer la qualité des résultats, et à traiter efficacement les données de séquençage afin de réduire la complexité du calcul. Plus précisément, nous proposons un nouvel algorithme pour quantifier la couverture maximale d'un génome atteignable par le séquençage, et nous appliquons cet algorithme à plusieurs génomes modèles. Nous formulons un ensemble de problèmes informatiques pour incorporer l'information des lectures pairées dans l'assemblage, et nous étudions leur complexité. Cette thèse introduit la notion d'assemblage localisé, qui consiste à construire et parcourir un graphe d'assemblage partiel. Pour économiser l'utilisation de la mémoire, nous utilisons des structures de données optimisées spécifiquement pour la tâche d'assemblage. Ces notions sont implémentées dans un nouvel assembleur de novo, Monument. Enfin, le dernier chapitre de cette thèse est consacré à des concepts d'assemblage dépassant l'assemblage de novo classique.
Type de document :
Thèse
Other [cs.OH]. École normale supérieure de Cachan - ENS Cachan, 2012. English. 〈NNT : 2012DENS0033〉
Liste complète des métadonnées

Littérature citée [54 références]  Voir  Masquer  Télécharger

https://tel.archives-ouvertes.fr/tel-00752033
Contributeur : Abes Star <>
Soumis le : mercredi 14 novembre 2012 - 16:47:33
Dernière modification le : vendredi 16 novembre 2018 - 01:40:37
Document(s) archivé(s) le : samedi 17 décembre 2016 - 10:15:02

Fichier

Chikhi2012.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-00752033, version 1

Citation

Rayan Chikhi. Computational methods for de novo assembly of next-generation genome sequencing data. Other [cs.OH]. École normale supérieure de Cachan - ENS Cachan, 2012. English. 〈NNT : 2012DENS0033〉. 〈tel-00752033〉

Partager

Métriques

Consultations de la notice

1248

Téléchargements de fichiers

423