Safe and complete contig assembly via omnitigs
Contig assembly is the first stage that most assemblers solve when reconstructing a genome from a set of reads. Its output consists of contigs -- a set of strings that are promised to appear in any genome that could have generated the reads. From the introduction of contigs 20 years ago, assemblers have tried to obtain longer and longer contigs, but the following question was never solved: given a genome graph $G$ (e.g. a de Bruijn, or a string graph), what are all the strings that can be safely reported from $G$ as contigs? In this paper we finally answer this question, and also give a polynomial time algorithm to find them. Our experiments show that these strings, which we call omnitigs, are 66% to 82% longer on average than the popular unitigs, and 29% of dbSNP locations have more neighbors in omnitigs than in unitigs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sneak peek at the tig sequences: useful sequences built from nucleic acid data
This manuscript is a tutorial on tig sequences that emerged after the name "contig", and are of diverse purposes in sequence bioinformatics. We review these different sequences (unitigs, simplitigs, monotigs, omnitigs to…
Graph Neural Networks for Microbial Genome Recovery
Microbes have a profound impact on our health and environment, but our understanding of the diversity and function of microbial communities is severely limited. Through DNA sequencing of microbial communities (metagenomi…
Towards complete representation of bacterial contents in metagenomic samples
Background: In the metagenome assembly of a microbiome community, we may think abundant species would be easier to assemble due to their deeper coverage. However, this conjucture is rarely tested. We often do not know ho…
DiversityViralQC: A Tool for Assessing Completeness and Contamination of Predicted Viral Contigs
Motivation: Viruses represent the most abundant biological entities on the planet and play vital roles in diverse ecosystems. Cataloging viruses across various environments is essential for understanding their properties…
EndHiC: assemble large contigs into chromosomal-level scaffolds using the Hi-C links from contig ends
Motivation: The application of PacBio HiFi and ultra-long ONT reads have achieved huge progress in the contig-level assembly, but it is still challenging to assemble large contigs into chromosomes with available Hi-C sca…