Aligning sequences via an evolutionary tree: complexity and approximation
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40) Problems related to evolution (92D15) Protein sequences, DNA sequences (92D20)
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
(35)- Approximation algorithms for constrained generalized tree alignment problem
- A combinatorial description of the closest tree algorithm for finding evolutionary trees
- On the approximability of the Steiner tree problem in phylogeny
- Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
- Approximation algorithms for multiple sequence alignment
- Walking tree heuristics for comparative genomic alignments.
- Fixed topology alignment with recombination
- Applying the Thorne-Kishino-Felsenstein model to sequence evolution on a star-shaped tree
- On approximating planar metrics by tree metrics.
- The minimal spanning tree preservation approaches for DNA multiple sequence alignment and evolutionary tree construction
- Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions
- Approximation algorithms for tree alignment with a given phylogeny
- A few logs suffice to build (almost) all trees. II
- On the complexity of sequence to graph alignment
- Counting, Generating and Sampling Tree Alignments
- An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
- Walking tree heuristics for biological string alignment, gene location, and phylogenies
- scientific article; zbMATH DE number 2185635 (Why is no real title available?)
- Trees, Stars, and Multiple Biological Sequence Alignment
- The Bottleneck Tree Alignment Problems
- On the low-dimensional Steiner minimum tree problem in Hamming metric
- scientific article; zbMATH DE number 1258199 (Why is no real title available?)
- scientific article; zbMATH DE number 1301590 (Why is no real title available?)
- scientific article; zbMATH DE number 1301592 (Why is no real title available?)
- Improved Approximation Algorithms for Tree Alignment
- Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
- A More Efficient Approximation Scheme for Tree Alignment
- Counting, Generating, Analyzing and Sampling Tree Alignments
- scientific article; zbMATH DE number 756194 (Why is no real title available?)
- Comparative Genomics
- Balanced vertices in trees and a simpler algorithm to compute the genomic distance
- On the approximability of the Steiner tree problem in phylogeny
- Novel evolutionary models and applications to sequence alignment problems
- Parametric multiple sequence alignment and phylogeny construction
- Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm
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)
