166 research outputs found
Dualities in Tree Representations
No full textA characterization of the tree T^* such that BP(T^*)=ova{DFUDS(T)}, the reversal of DFUDS(T) is given. An immediate consequence is a rigorous characterization of the tree T^ such that BP(T^)=DFUDS(T). In summary, BP and DFUDS are unified within an encompassing framework, which might have the potential to imply future simplifications with regard to queries in BP and/or DFUDS. Immediate benefits displayed here are to identify so far unnoted commonalities in most recent work on the Range Minimum Query problem, and to provide improvements for the Minimum Length Interval Query problem
Disk Compression of k-mer Sets
No full textK-mer based methods have become prevalent in many areas of bioinformatics. In applications such as database search, they often work with large multi-terabyte-sized datasets. Storing such large datasets is a detriment to tool developers, tool users, and reproducibility efforts. General purpose compressors like gzip, or those designed for read data, are sub-optimal because they do not take into account the specific redundancy pattern in k-mer sets. In our earlier work (Rahman and Medvedev, RECOMB 2020), we presented an algorithm UST-Compress that uses a spectrum-preserving string set representation to compress a set of k-mers to disk. In this paper, we present two improved methods for disk compression of k-mer sets, called ESS-Compress and ESS-Tip-Compress. They use a more relaxed notion of string set representation to further remove redundancy from the representation of UST-Compress. We explore their behavior both theoretically and on real data. We show that they improve the compression sizes achieved by UST-Compress by up to 27 percent, across a breadth of datasets. We also derive lower bounds on how well this type of compression strategy can hope to do
Supplemental Material for Martchenko, Chikhi, and Shafer, 2020
No full textSupplemental Material for Martchenko, Chikhi, and Shafer, 202
Dualities in Tree Representations
No full textChikhi R, Schönhuth A. Dualities in Tree Representations. arXiv:1804.04263. 2018.A characterization of the tree such that
, the reversal of
is given. An immediate consequence is a rigorous
characterization of the tree such that
. In summary, and
are unified within an encompassing framework, which might have
the potential to imply future simplifications with regard to queries in
and/or . Immediate benefits displayed here are to
identify so far unnoted commonalities in most recent work on the Range Minimum
Query problem, and to provide improvements for the Minimum Length Interval
Query problem
Des séquences au connaissances, améliorer et apprendre des alignements de séquences
No full textDans cette thèse nous étudierons deux problèmes importants en bioinformatique, le premier concernant l’analyse primaire de données de séquençage, 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équençage 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èmes 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 répandu. 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’humains, de drosophiles et d’E. coli. L’amélioration des méthodes d’alignement de séquences est cruciale pour les analyses en aval .Par exemple, les alignements de séquences multiples sont indispensables pour étudier la 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 avons identifié des mutations de résistance aux médicaments. Nous avons ensuite, avant l’entraînement, supprimé le signal connu et associé à la pharmacoressitance des données. Nous conservons le pouvoir discriminant des classificateurs, et avons identifié 6 nouvelles mutations associées à la résistance. Une étude plus approfondie a indiqué que celles-ci étaient très probablement de nature accessoire et liées à des mutations de résistance connues.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 prevalent 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 resistance in viruses with machine learning methods. We used a very large multiple sequence alignment of British HIV sequences and trained multiple classifiers to discriminate between treatment-naive and treatment-experienced sequences. By studying important classifier features we identified drug resistance mutations. We then removed known drug resistance associated signal from the data before training, kept 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
Algorithmes basés sur les k-mères pour la métagénomique orale ancienne : outils pour l'élimination et l'évaluation de la contamination en paléométagénomique
No full textLa paléométagénomique est l'étude du matériel génétique ancien à l'aide du séquençage métagénomique, un processus qui implique la caractérisation de l'ADN de tous les organismes d'un échantillon. Par matériel génétique ancien, nous entendons l'ADN provenant d'une source non vivante et présentant des signes de dégradation moléculaire. Le tartre dentaire s'est révélé être une source exceptionnellement riche d'ADN ancien et a été utilisé pour étudier l'évolution du microbiome buccal, ainsi que la santé bucco-dentaire et l'alimentation de l'homme. Malgré la mise en place de protocoles de laboratoire rigoureux pour le contrôle de la contamination de l'ADN ancien, les échantillons d'ADN ancien court sont encore très sensibles à la contamination par des sources environnementales, ce qui peut modifier radicalement la composition microbienne et conduire à des conclusions erronées après les analyses en aval. Cette thèse propose deux algorithmes qui s'appuient sur les k-mers (sous-séquences d'ADN) pour relever deux défis importants dans le domaine de la paléométagénomique : l'évaluation de la contamination via le suivi des sources microbiennes et l'élimination de la contamination au niveau des lectures. La première tâche a donné lieu à une publication en première auteure et à un logiciel ouvert appelé decOM, tandis que la seconde a également été publiée en tant qu'article du première auteure accompagné d'un logiciel ouvert appelé aKmerBroom. Les deux méthodes ont été testées sur des données métagénomiques orales anciennes, mais leur utilité peut être étendue à des échantillons qui ne proviennent pas de sources orales anciennes. Dans l'ensemble, cette thèse a prouvé que les algorithmes basés sur k-mer ont un immense potentiel pour l'élimination de la contamination et l'évaluation de la contamination des métagénomes, car ils tirent parti de la richesse des informations métagénomiques qui ont été séquencées et mises à la disposition du public au fil des ans.Palaeometagenomics is the study of ancient genetic material by using metage- nomic sequencing, a process that entails the characterisation of the DNA from all the organisms in a sample. By ancient genetic material we refer to the DNA that comes from a non-living source and that shows signs of molecular degradation. Dental calculus has proven to be an exceptionally rich source of ancient DNA (aDNA) and it has been used to investigate the evolution of the oral microbiome, as well as human oral health and diet. Despite the establishment of rigorous laboratory protocols for aDNA contamination control, aDNA samples are still highly susceptible to contamination from environmental sources, which can drastically alter the microbial composition and lead to erroneous conclusions after downstream analyses. This dissertation proposes two algorithms that rely on k-mers (sub-sequences of DNA) to address two relevant challenges in the field of palaeometagenomics: contamination assessment via Microbial Source Tracking and contamination removal at the read level. The former task resulted in a first-author publication and an open-software called decOM, while the latter has also been published as a first-author paper accompanied by an open-software called aKmerBroom. Both methods were tested on ancient oral metagenomic data, yet their utility can be extended to samples that do not originate from ancient oral sources. Overall, this thesis has proven that k-mer-based algorithms have an immense potential for contamination removal and contamination assessment of metagenomes, as they leverage the wealth of metagenomic information that has been sequenced and made publicly available throughout the years
Analyse de graphes pangénomiques humains
No full textDepuis plus de vingt ans, le génome Humain de référence a jeté les bases de la recherche en génomique Humaine. Toutefois, la quantité d'informations extraite de cette référence est limitée par sa non complétude et ses morceaux issus de simulations. En 2022, le consortium Telomere-to-Telomere a franchi une étape importante en publiant la première séquence complète d'un haploïde Humain(T2T-CHM13), ce qui a permis de faire de nouvelles découvertes sur les régions du génome qui étaient auparavant manquantes. Néanmoins, un seul génome ne peut pas représenter de manière adéquate l'ensemble de la diversité génétique au sein de la population Humaine, en particulier les grands variants structuraux. Pour remédier au biais de référence inhérent à l'utilisation d'un seul génome comme moyen de comparaison, la communauté scientifique s'oriente vers les pangénomes : il s'agit de modèles qui englobent de multiples allèles provenant d'une collection de génomes. Le domaine de la pangénomique computationnelle vise à trouver de nouveaux modèles de pangénomes plus efficaces qui peuvent améliorer les résultats des analyses basées sur les références. Entre autres, la représentation la plus courante du pangénome est basée sur les graphes. Cette thèse présente deux contributions principales à la pangénomique computationnelle. La première est une analyse comparative des représentations graphiques du pangénome, basée sur la construction du plus grand graphique du pangénome à ce jour. Cette analyse compare différents modèles de graphes, en utilisant cinq outils de pointe, mettant en lumière les principales différences entre les représentations, en particulier sur la façon dont elles capturent la variation génétique dans les loci complexes. La deuxième contribution porte sur les structures de données avancées pour la représentation des ensembles de k-mer. En particulier, trois nouvelles structures de données visent à améliorer l'association des métadonnées, l'accessibilité des analyses en aval et la scalabilité. Ces méthodes basées sur les kmer visent à faciliter les analyses génomiques et pangénomiques. Cette thèse présente ma contribution à l'évolution en cours de la recherche en pangénomique computationnelle.For over two decades, the human reference genome has laid the ground for human genomic research. However, its power to provide insights has been constrained by the presence of gaps and simulated sequences. In 2022, the Telomere-to-Telomere consortium achieved an important milestone by releasing the first full sequence of an haploid human genome (T2T-CHM13), empowering a new discoveries on the previously missing regions of the genome. Nevertheless, a single genome cannot adequately represent the entire genetic diversity within the human population, in particular large structural variants. To address the inherent reference bias of using a single genome as mean of comparison, the scientific community is transitioning towards pangenomes: these are models that encapsulate multiple alleles from a collection of genomes. The field of computational pangenomics aims at finding new and more efficient pangenome models that can improve the results of reference-based analyses. Among others, the most common pangenome representation is based on graphs. This dissertation presents two primary contributions to computational pangenomics. The first is a comparative analysis of pangenome graph representations, based on the construction of the largest pangenome graph to that date. This analysis compares different graph models, using five state-of-the-art tools, shed-ding light on key differences between the representation, particularly on how they capture genetic variation in complex loci. The second contribution focuses on advanced data structures for k-mer sets representation. In particular, on three novel data structures that focus on improving metadata association, downstream analysis accessibility and scalability. Thesek-mer-based methods aim at facilitating genomic and pangenomic analyses. This dissertation present my contributes to the ongoing evolution of computational pangenomics research
Méthodes de calcul pour assemblage de novo de nouvelle génération des techniques de séquençage du génome
No full textIn this thesis, we discuss computational methods (theoretical models and algorithms) to perform the reconstruction (de novo assembly) of DNA sequences produced by high-throughput sequencers. This problem is challenging, both theoretically and practically. The theoretical difficulty arises from the complex structure of genomes. The assembly process has to deal with reconstruction ambiguities. The output of sequencing predicts up to an exponential number of reconstructions, yet only one is correct. To deal with this problem, only a fragmented approximation of the genome is returned. The practical difficulty stems from the huge volume of data produced by sequencers, with high redundancy. Significant computing power is required to process it. As larger genomes and meta-genomes are being sequenced, the need for efficient computational methods for de novo assembly is increasing rapidly. This thesis introduces novel contributions to genome assembly, both in terms of incorporating more information to improve the quality of results, and efficiently processing data to reduce the computation complexity. Specifically, we propose a novel algorithm to quantify the maximum theoretical genome coverage achievable by sequencing data (paired reads), and apply this algorithm to several model genomes. We formulate a set of computational problems that take into account pairing information in assembly, and study their complexity. Then, two novel concepts that cover practical aspects of assembly are proposed: localized assembly and memory-efficient reads indexing. Localized assembly consists in constructing and traversing a partial assembly graph. These ingredients are implemented in a complete de novo assembly software package, the Monument assembler. Monument is compared with other state of the art assembly methods. Finally, we conclude with a series of smaller projects, exploring concepts beyond classical de novo assembly.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
Paired-end read length lower bounds for genome re-sequencing
No full textInternational audienceNext-generation sequencing technology is enabling massive production of high-quality paired-end reads. Many platforms (Illumina Genome Analyzer, Applied Biosystems SOLID, Helicos HeliScope) are currently able to produce "ultra-short" paired reads of lengths starting at 25 nt. An analysis by Whiteford et al. [1] on sequencing using unpaired reads shows that ultra-short reads theoretically allow whole genome re-sequencing and de novo assembly of only small eukaryotic genomes. By conducting an analysis extending Whiteford et al. results, we investigate to what extent genome re-sequencing is feasible with ultra-short paired reads. We obtain theoretical read length lower bounds for re-sequencing that are also applicable to paired-end de novo assembly
- …
