Approximation algorithms for tree alignment with a given phylogeny

DOI10.1007/BF01955679zbMath0862.68119MaRDI QIDQ1924406

Lusheng Wang, Tao Jiang, Eugene L. Lawler

Publication date: 25 May 1997

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

computational biology; Steiner trees; phylogenetic tree; computational molecular biology; evolutionary tree; tree alignment

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68U99: Computing methodologies and applications

Related Items

Near optimal multiple alignment within a band in polynomial time, The consensus string problem for a metric is NP-complete, Approximation algorithms for constrained generalized tree alignment problem, Approximation algorithms for reconstructing the duplication history of tandem repeats, Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree, Fixed topology alignment with recombination, Methods for reconstructing the history of tandem repeats and their application to the human genome., A few logs suffice to build (almost) all trees. II, Topology of strings: median string is NP-complete, Hardness results for the center and median string problems under the weighted and unweighted edit distances, A SURVEY ON ALGORITHMIC ASPECTS OF TANDEM REPEATS EVOLUTION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Line geometries for sequence comparisons
• The Steiner problem with edge lengths 1 and 2
• Optimization, approximation, and complexity classes
• A survey of multiple sequence comparison methods
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Trees, Stars, and Multiple Biological Sequence Alignment
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• The Multiple Sequence Alignment Problem in Biology
• The shortest network under a given topology
• Minimal Mutation Trees of Sequences
• Locating the vertices of a steiner tree in an arbitrary metric space
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Mapping the genome
• Steiner tree problems