Multiple Alignment, Communication Cost, and Graph Matching

DOI10.1137/0152101MaRDI QIDQ4037677zbMATH OpenOpenAlexFDO

Authors Pavel 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

approximation algorithmsbiological sequencesdynamic programmingmaximum matchingsequence alignment

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of sequence to graph alignment
• On graph-based data structures to multiple genome alignment
• Scalable algorithms for multiple network alignment
• Approximation algorithms for multiple sequence alignment
• Local multiple alignment via subgraph enumeration
• On the number of many-to-many alignments of multiple sequences
• Multiple sequence comparison and consistency on multipartite graphs
• An optimization approach to multiple sequence alignment

Cited in

(25)

• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Enhanced \(A^{*}\) algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary 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.
• An optimization approach to multiple sequence alignment
• Approximation algorithms for the shortest total path length spanning tree problem
• Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions
• Finding similar regions in many sequences
• On the uniform edge-partition of a tree
• On the complexity of sequence to graph alignment
• scientific article; zbMATH DE number 1615272 (Why is no real title available?)
• Multiple sequence alignment as a facility-location problem
• Restricted common superstring and restricted common supersequence
• Alignment between two multiple alignments
• A multiple alignment approach for DNA sequences based on maximum weighted path algorithms
• Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles)
• Multiple alignment of biological sequences with gap flexibility
• scientific article; zbMATH DE number 2243049 (Why is no real title available?)
• scientific article; zbMATH DE number 2243390 (Why is no real title available?)
• Near optimal multiple alignment within a band in polynomial time
• Local multiple alignment via subgraph enumeration
• Novel evolutionary models and applications to sequence alignment problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4037677)