Multiple Alignment, Communication Cost, and Graph Matching

DOI10.1137/0152101zbMath0766.68064OpenAlexW1987663950MaRDI QIDQ4037677

Pavel A. Pevzner

Publication date: 16 May 1993

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

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

zbMATH Keywords

dynamic programmingmaximum matchingbiological sequencesapproximation algorithmssequence alignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Protein sequences, DNA sequences (92D20)

Related Items (10)

On the uniform edge-partition of a tree ⋮ Approximation algorithms for multi-index transportation problems with decomposable costs ⋮ The parameterized complexity of sequence alignment and consensus ⋮ Approximation algorithms for multiple sequence alignment ⋮ The approximate period problem for DNA alphabet. ⋮ Restricted Common Superstring and Restricted Common Supersequence ⋮ 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 ⋮ Finding similar regions in many sequences

This page was built for publication: Multiple Alignment, Communication Cost, and Graph Matching