Improved Approximation Algorithms for Tree Alignment

DOI10.1006/jagm.1997.0882zbMath0895.68061OpenAlexW2099430820MaRDI QIDQ4373002

Lusheng Wang, Dan Gusfield

Publication date: 8 September 1998

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/fd9cc6a1bf86a5fba7ea4b449c252fbb7f5ffb72

zbMATH Keywords

multiple sequence alignmenttree alignment problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (9)

A few logs suffice to build (almost) all trees. II ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ A SURVEY ON ALGORITHMIC ASPECTS OF TANDEM REPEATS EVOLUTION ⋮ Approximation algorithms for constrained generalized tree alignment problem ⋮ Near optimal multiple alignment within a band in polynomial time ⋮ Large-Scale Multiple Sequence Alignment and Phylogeny Estimation ⋮ An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees ⋮ Hardness results for the center and median string problems under the weighted and unweighted edit distances ⋮ Fixed topology alignment with recombination

This page was built for publication: Improved Approximation Algorithms for Tree Alignment