Approximation algorithms for tree alignment with a given phylogeny

DOI10.1007/BF01955679zbMath0862.68119OpenAlexW2120154580MaRDI QIDQ1924406

Lusheng Wang, Tao Jiang, Eugene L. Lawler

Publication date: 25 May 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01955679

zbMATH Keywords

computational biologySteiner treesphylogenetic treecomputational molecular biologyevolutionary treetree alignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99)

Related Items

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

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