Approximation algorithms for multiple sequence alignment

DOI10.1016/S0304-3975(97)00023-6zbMath0911.68070OpenAlexW2035806546MaRDI QIDQ1391132

Vineet Bafna, Pavel A. Pevzner, Eugene L. Lawler

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00023-6

zbMATH Keywords

randomized algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (9)

On the uniform edge-partition of a tree ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Non-approximability of weighted multiple sequence alignment. ⋮ A cost-aggregating integer linear program for motif finding ⋮ Constrained sequence alignment: A general model and the hardness results ⋮ The complexity of multiple sequence alignment with SP-score that is a metric ⋮ Near optimal multiple alignment within a band in polynomial time ⋮ Non-approximability of weighted multiple sequence alignment for arbitrary metrics ⋮ Approximation algorithms for the shortest total path length spanning tree problem

Cites Work

• A survey of multiple sequence comparison methods
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Some biological sequence metrics
• Universal classes of hash functions
• Aligning sequences via an evolutionary tree
• Trees, Stars, and Multiple Biological Sequence Alignment
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• Multiple Alignment, Communication Cost, and Graph Matching
• Minimal Mutation Trees of Sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for multiple sequence alignment