An Eulerian path approach to DNA fragment assembly
From MaRDI portal
Publication:4547675
DOI10.1073/pnas.171285098zbMath0993.92018OpenAlexW2136651963WikidataQ24555762 ScholiaQ24555762MaRDI QIDQ4547675
Pavel A. Pevzner, Michael S. Waterman, Haixu Tang
Publication date: 11 September 2002
Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)
Full work available at URL: http://www.pnas.org/content/vol98/issue17/#APPLIED_MATHEMATICS
Applications of graph theory (05C90) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Eulerian and Hamiltonian graphs (05C45)
Related Items
GTED: Graph Traversal Edit Distance ⋮ AN EFFICIENT ALGORITHM FOR CHINESE POSTMAN WALK ON BI-DIRECTED DE BRUIJN GRAPHS ⋮ A fast algorithm for the construction of universal footprinting templates in DNA ⋮ Next generation sequencing under de novo genome assembly ⋮ An Eulerian path approach to local multiple alignment for DNA sequences ⋮ On the Sound Covering Cycle Problem in Paired de Bruijn Graphs ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ Bidirectional Variable-Order de Bruijn Graphs ⋮ MetaCoAG: binning metagenomic contigs via composition, coverage and assembly graphs ⋮ Safety and completeness in flow decompositions for RNA assembly ⋮ Block structure and stability of the genetic code ⋮ Graph algorithms for DNA sequencing -- origins, current models and the future ⋮ The principles of informational genomics ⋮ On the domination number of $t$-constrained de Bruijn graphs ⋮ VStrains: de novo reconstruction of viral strains via iterative path extraction from assembly graphs ⋮ The simplified partial digest problem: approximation and a graph-theoretic model ⋮ Bounding the number of Eulerian tours in undirected graphs ⋮ Linking indexing data structures to de Bruijn graphs: construction and update ⋮ Linear-time superbubble identification algorithm for genome assembly ⋮ Towards a theory of patches ⋮ Approximate all-pairs suffix/prefix overlaps ⋮ An embedding technique in the study of word-representability of graphs ⋮ Construction of de Bruijn sequences from product of two irreducible polynomials ⋮ Failed zero forcing and critical sets on directed graphs ⋮ A one pass streaming algorithm for finding Euler tours ⋮ Refined bounds on the number of Eulerian tours in undirected graphs ⋮ Genetic code from tRNA point of view ⋮ On the complexity of the Eulerian closed walk with precedence path constraints problem ⋮ Four-regular graphs with rigid vertices associated to DNA recombination ⋮ On the Query Complexity of Testing Orientations for Being Eulerian ⋮ Collapsing Superstring Conjecture ⋮ Modified classical graph algorithms for the DNA fragment assembly problem ⋮ DNA-Seq Error Correction Based on Substring Indices ⋮ The Contig Assembly Problem and Its Algorithmic Solutions ⋮ Global optimization for scaffolding and completing genome assemblies ⋮ Scaling metagenome sequence assembly with probabilistic de Bruijn graphs ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Unnamed Item ⋮ Consensus on de Bruijn graphs ⋮ Alignment-free sequence comparison using absent words ⋮ Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree ⋮ Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis ⋮ Safe and Complete Contig Assembly Via Omnitigs ⋮ Edge-Matching Problems with Rotations ⋮ Synteny Paths for Assembly Graphs Comparison ⋮ Disentangled Long-Read De Bruijn Graphs via Optical Maps ⋮ On the complexity of approximately matching a string to a directed graph ⋮ The complexity of string partitioning ⋮ Walk-preserving transformation of overlapped sequence graphs into blunt sequence graphs with GetBlunted ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs
Uses Software
Cites Work
