Trees, Stars, and Multiple Biological Sequence Alignment

DOI10.1137/0149012zbMath0695.92006OpenAlexW1967762061WikidataQ113779254 ScholiaQ113779254MaRDI QIDQ3471898

Stephen F. Altschul, David J. Lipman

Publication date: 1989

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0149012

zbMATH Keywords

protein sequencesmolecular biologynucleic acid sequencestree topologiesbranch and bound inequalitiesCarrillo-Lipman inequalitycost of an evolutionary treemultiple alignment costoptimal multiple sequence alignmentstar topologies

Mathematics Subject Classification ID

Linear programming (90C05) Dynamic programming (90C39) Physiological, cellular and medical topics (92Cxx)

Related Items (18)

The consensus string problem for a metric is NP-complete ⋮ Parametric multiple sequence alignment and phylogeny construction ⋮ Approximation algorithms for tree alignment with a given phylogeny ⋮ Multiple sequence comparison -- a peptide matching approach ⋮ Approximation algorithms for multiple sequence alignment ⋮ Consistency of optimal sequence alignments ⋮ A survey of multiple sequence comparison methods ⋮ Efficient methods for multiple sequence alignment with guaranteed error bounds ⋮ A multiple sequence comparison method ⋮ Efficient algorithms for consensus string problems minimizing both distance sum and radius ⋮ Comparison of strings belonging to the same family ⋮ 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 ⋮ On computing all suboptimal alignments ⋮ Fixed topology alignment with recombination ⋮ The computation of consensus patterns in \(DNA\) sequences ⋮ A measure of discrepancy of multiple sequences

This page was built for publication: Trees, Stars, and Multiple Biological Sequence Alignment