Combinatorial algorithms for DNA sequence assembly

DOI10.1007/BF01188580zbMath0831.92013MaRDI QIDQ1902464

Eugene W. Myers, John D. Kececioglu

Publication date: 12 February 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

multiple sequence alignmentapproximation algorithmsbranch-and-bound algorithmssequence reconstructionDNA sequence assemblyshortest common superstring problemfour-phase approachfragment assemblysequencing error rates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Related Items (22)

Uniform words ⋮ COVERS FROM TEMPLATES ⋮ On the distribution of characteristic parameters of words II ⋮ An Eulerian path approach to DNA fragment assembly ⋮ Unnamed Item ⋮ Safety and completeness in flow decompositions for RNA assembly ⋮ Minimax regret spanning arborescences under uncertain costs ⋮ Classification of de Bruijn-based labeled digraphs ⋮ On the role of metaheuristic optimization in bioinformatics ⋮ Approximate all-pairs suffix/prefix overlaps ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ On the complexity of the Eulerian closed walk with precedence path constraints problem ⋮ The Contig Assembly Problem and Its Algorithmic Solutions ⋮ Characterizing the reconstruction and enumerating the patterns of DNA sequences with re\-peats ⋮ Optimal prefix and suffix queries on texts ⋮ Unnamed Item ⋮ Rearrangement of DNA fragments: a branch-and-cut algorithm. ⋮ Safe and Complete Contig Assembly Via Omnitigs ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ Fuzzy Genome Sequence Assembly for Single and Environmental Genomes ⋮ Practical lower and upper bounds for the Shortest Linear Superstring ⋮ Diagram processing: Computing with diagrams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for finding approximate shortest common superstrings
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• The pairing heap: A new form of self-adjusting heap
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• An efficient algorithm for the all pairs suffix-prefix problem
• Approximation algorithms for the shortest common superstring problem
• A note on finding optimum branchings
• Thek best spanning arborescences of a network
• Longest common subsequences of two random sequences
• Minimal Mutation Trees of Sequences
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Finding optimum branchings
• Linear approximation of shortest superstrings
• An Algorithm for Reconstructing Protein and RNA Sequences
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem

This page was built for publication: Combinatorial algorithms for DNA sequence assembly