Continuous embeddings for large-scale machine learning with DNA sequences
Représentations pour l'apprentissage statistique à grande échelle en génomique
Résumé
The cost of DNA sequencing has been divided by 100,000 in the past 15 years. Brought along by this technological revolution, ever larger volumes of data are coming in from diverse fields and problems, raising new computational challenges. How can we efficiently store and analyze DNA sequences? A modern DNA sequencing experiment outputs billions of short DNA fragments (reads), in random order. A crucial step in the bioinformatics analysis pipeline is to match those fragments to their parent genomes, a problem called taxonomic binning. Up until a few years ago alignment-based strategies were the norm, which were largely based on string-matching algorithms. However these have become too slow for the ever-growing amount of available sequenced genomes. More recently so-called pseudo-alignment strategies have become standard. These hold databases of large sub-strings and look for matches in the query sequences. Machine learning methods have shown promising success in classifying biological sequences and in this thesis we will investigate these methods for taxonomic binning. Firstly, we present an algorithm, fastDNA{}, that embeds sequences in a continuous vector space by first splitting them into short kmers{} (substrings of length k) and learning an embedding for each kmer{}. The embedding is then run through a linear classifier. In the second part of this thesis we will present Brume{}, an extension to fastDNA{} that allow for longer k-mers, using the de Bruijn graph. Finally we will introduce Phylo-HS, a structured loss for neural network-based taxonomic classification.
Le coût du séquençage de l'ADN a été divisé par 100 000 en seulement 15 ans. Grâce à cette révolution technologique, des volumes de données toujours plus grands émergent, posant de nouvelles problématiques informatiques. Comment analyser et stocker les séquences d'ADN de manière efficiente ? La métagénomique, qui cherche à caractériser et identifier les microbes – bactéries, virus – à partir de leur ADN, a largement bénéficié de cette avancée. Une expérience de séquençage produit des milliards de petits fragments d'ADN (reads), mélangés aléatoirement. Une étape cruciale en bioinformatique est d'identifier le génome d'origine de chaque fragment, un problème dit de taxonomic binning. Les méthodes classiques, basées sur l’alignement des séquences à des génomes de référence, devenues trop lentes avec l’augmentation du nombre de génomes, ont été remplacées par le pseudo-alignement. Celui-ci cherche des sous-séquences du read dans une base préexistante. L'apprentissage statistique offre également des résultats prometteurs pour la classification des séquences biologiques. Dans cette thèse, nous approfondirons ces méthodes pour le taxonomic binning. Nous présenterons d’abord fastDNA, un algorithme qui apprend des représentations continues pour tous les k-mers (courtes sous-séquences de longueur k, ou "mots" de l'ADN). Une représentation vectorielle du read est obtenue en combinant celles de ses k-mers, et un classifieur linéaire en prédit la classe. Ensuite, nous introduirons Brume, une extension de fastDNA qui regroupe les k-mers via le graphe de de Bruijn, augmentant le nombre de k-mers effectifs sans surcoût mémoire. Enfin, nous présenterons Phylo-HS, une nouvelle fonction d’apprentissage statistique basée sur l’arbre phylogénétique.
Origine | Version validée par le jury (STAR) |
---|