Abstract

In this thesis we study two important problems in computational biology, one pertaining to primary analysis of sequencing data, and the second pertaining to secondary analysis of sequences to obtain biological insights using machine-learning. Sequence alignment is one of the most powerful and important tools in the field of computational biology. Read alignment is often the first step in many analyses like structural variant detection, genome assembly or variant calling. Long read sequencing technologies have improved the quality of results across all these analyses. They remain, however, plagued by sequencing errors and pose algorithmic challenges to alignment. A prevalent technique to reduce the detrimental effects of these errors is homopolymer compression, which targets the most common type of long-read sequencing error. We present a more general framework than homopolymer compression, which we call mapping-friendly sequence reductions (MSR). We then show that some of these MSRs improve the accuracy of read alignments across whole human, drosophila and E. coli genomes. Improvements in sequence alignment methods are crucial for downstream analyses. For instance, multiple sequence alignments are indispensable when studying resistance in viruses. With the ever growing quantity of annotated, high-quality multiple sequence alignments it has become possible and useful to study drug resistance in viruses with machine learning methods. We used a very large multiple sequence alignment of British HIV sequences to train multiple classifiers to discriminate between treatment-naive and treatment-experienced sequences. By studying important classifier features we identified resistance-associated mutations. We then removed known drug resistance associated signal from the data before training, keeping classifying power, and identified 6 novel resistance associated mutations. Further study indicated that these were most likely accessory in nature and linked to known resistance mutations.

Résumé

Dans cette thèse nous étudierons deux problèmes importants en bioinformatique, le premier concernant l’analyse primaire de données de séquencage, et le second concernant l’analyse secondaire de séquence par apprentissage automatique en vue d’obtenir des connaissances biologiques. L’alignement de séquences est l’un des outils les plus puissants et les plus importants dans le domaine de la biologie computationnelle. L’alignement de lectures de séquencage est souvent la première étape de nombreuses analyses telles que la détection de variations de structure, ou l’assemblage de génomes. Les technologies de séquençage à longue lectures ont amélioré la qualité des résultats pour toutes ces analyses. Elles sont, cependant, riches en erreurs de séquençage et posent des problèms algorithmiques à l’alignement. Une technique répandue pour réduire les effets néfastes de ces erreurs est la compression d’homopolymères. Cette technique cible le type d’erreur de séquençage à longue lectures le plus fréquent. Nous présentons une technique plus générale que la compression d’homopolymères, que nous appelons les “mapping-friendly sequence reductions” (MSR). Nous montrons ensuite que certaines de ces MSRs améliorent la précision des alignements de lecture sur des génomes entiers d’humain, de drosophile et d’E. coli. L’amélioration des méthodes d’alignment de séquences est cruciale pour les analyses en aval. Par exemple, les alignements de séquences multiples sont indispensables pour étudier la pharmaco-résistance des virus. Grâce à la quantité toujours croissante d’alignements de séquences multiples annotés et de haute qualité, il est aujourd’hui devenu possible et utile d’étudier la résistance des virus à l’aide de méthodes d’apprentissage automatique. Nous avons utilisé un très grand alignement de séquences multiples de séquences de VIH britanniques et entraîné plusieurs classificateurs pour distinguer les séquences non-traitées des séquences traitées. En étudiant les variables importantes aux classificateurs, nous identifions des mutations associées à la résistance. Nous avons ensuite supprimé des données, avant l’entraînement, le signal de pharmaco-résistance connu. Nous conservons le pouvoir discriminant des classificateurs, et avons identifié 6 nouvelles mutations associées à la résistance. Une étude plus approfondie a montré que celles-ci étaient très probablement accessoires et liées à des mutations de résistance connues.