Aligning sequences via an evolutionary tree: complexity and approximation

DOI10.1145/195058.195454MaRDI QIDQ2817672zbMATH OpenOpenAlexFDO

Authors Tao Jiang, Lusheng Wang, Eugene L. Lawler

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195058.195454

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Problems related to evolution (92D15) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Recommendations

• Approximation algorithms for tree alignment with a given phylogeny
• scientific article; zbMATH DE number 1088267
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
• On the complexity of constructing evolutionary trees
• A More Efficient Approximation Scheme for Tree Alignment

Cited in

(31)

• On the low-dimensional Steiner minimum tree problem in Hamming metric
• On the complexity of sequence to graph alignment
• Fixed topology alignment with recombination
• Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions
• Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm
• On the approximability of the Steiner tree problem in phylogeny
• Parametric multiple sequence alignment and phylogeny construction
• scientific article; zbMATH DE number 756194 (Why is no real title available?)
• Counting, Generating, Analyzing and Sampling Tree Alignments
• Comparative Genomics
• Walking tree heuristics for comparative genomic alignments.
• An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Novel evolutionary models and applications to sequence alignment problems
• Applying the Thorne-Kishino-Felsenstein model to sequence evolution on a star-shaped tree
• A few logs suffice to build (almost) all trees. II
• Balanced vertices in trees and a simpler algorithm to compute the genomic distance
• A combinatorial description of the closest tree algorithm for finding evolutionary trees
• The minimal spanning tree preservation approaches for DNA multiple sequence alignment and evolutionary tree construction
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
• On the approximability of the Steiner tree problem in phylogeny
• Approximation algorithms for constrained generalized tree alignment problem
• The Bottleneck Tree Alignment Problems
• Walking tree heuristics for biological string alignment, gene location, and phylogenies
• Approximation algorithms for tree alignment with a given phylogeny
• A More Efficient Approximation Scheme for Tree Alignment
• scientific article; zbMATH DE number 2185635 (Why is no real title available?)
• On approximating planar metrics by tree metrics.
• Trees, Stars, and Multiple Biological Sequence Alignment
• Counting, Generating and Sampling Tree Alignments
• Approximation algorithms for multiple sequence alignment

This page was built for publication: Aligning sequences via an evolutionary tree: complexity and approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817672)