Efficient methods for multiple sequence alignment with guaranteed error bounds

DOI10.1007/BF02460299zbMath0756.92020OpenAlexW4255011371WikidataQ38573713 ScholiaQ38573713MaRDI QIDQ1203038

Dan Gusfield

Publication date: 11 February 1993

Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)

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

zbMATH Keywords

amino acidsbiological sequencesRNArandomized methodmultiple string alignmentstrings of DNA

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Related Items (27)

On the uniform edge-partition of a tree ⋮ Exact algorithms for minimum routing cost trees ⋮ Constrained pairwise and center-star sequences alignment problems ⋮ On some optimization problems in molecular biology ⋮ Approximation algorithms for multi-index transportation problems with decomposable costs ⋮ The parameterized complexity of sequence alignment and consensus ⋮ Improving the divide-and-conquer approach to sum-of-pairs multiple sequence alignment ⋮ 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 ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Multiple sequence comparison -- a peptide matching approach ⋮ Approximation algorithms for multiple sequence alignment ⋮ Non-approximability of weighted multiple sequence alignment. ⋮ On the minimum average distance spanning tree of the hypercube ⋮ Constrained sequence alignment: A general model and the hardness results ⋮ The complexity of multiple sequence alignment with SP-score that is a metric ⋮ Parallel Algorithms to Align Multiple Strings in the Context of Web Data Extraction ⋮ Local multiple alignment via subgraph enumeration ⋮ Integer Linear Programming in Computational Biology ⋮ 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 ⋮ Approximation algorithms for the shortest total path length spanning tree problem ⋮ Hardness results for the center and median string problems under the weighted and unweighted edit distances ⋮ Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions ⋮ Finding similar regions in many sequences

Cites Work

• Unnamed Item
• A fast algorithm for Steiner trees
• 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
• Worst-Case Analysis of Network Design Problem Heuristics

This page was built for publication: Efficient methods for multiple sequence alignment with guaranteed error bounds