Multiple Alignment, Communication Cost, and Graph Matching

DOI10.1137/0152101zbMATH Open0766.68064OpenAlexW1987663950MaRDI QIDQ4037677FDOQ4037677

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

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

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)

Cited In (24)

• On the complexity of sequence to graph alignment
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)