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

dynamic programmingapproximation algorithmsmaximum matchingsequence alignmentbiological sequences

Mathematics Subject Classification ID

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

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

(24)

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

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)