On computing all suboptimal alignments

DOI10.1016/S0020-0255(97)10032-9MaRDI QIDQ1291563zbMATHOpenAlexFDO

Authors Kun-Mao Chao

Publication date 20 September 2000

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0255(97)10032-9

zbMATH Keywords

divide-and-conquersequence comparisonlinear-space algorithmminimal directed acyclic graphsuboptimal alignments

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Biochemistry, molecular biology (92C40) Dynamic programming (90C39) Parallel algorithms in computer science (68W10) Computational methods for problems pertaining to biology (92-08)

Recommendations

• On all-substrings alignment problems
• General space-efficient sampling algorithm for suboptimal alignment
• scientific article; zbMATH DE number 2119727
• Lower bounds for optimal alignments of binary sequences
• Optimal alignments of longest common subsequences and their path properties
• On the complexity of constrained sequences alignment problems
• An optimization approach to multiple sequence alignment
• scientific article; zbMATH DE number 45430
• Optimal sequence alignment using affine gap costs
• Approximation algorithms for multiple sequence alignment

Cites work

• A dynamic programming algorithm to find all solutions in a neighborhood of the optimum
• A linear space algorithm for computing maximal common subsequences
• Approximate matching of regular expressions
• Efficient Parallel Algorithms for String Editing and Related Problems
• Efficient string matching
• Linear-space algorithms that build local alignments from fragments
• Optimized homology searches of the gene and protein sequence data banks
• The Multiple Sequence Alignment Problem in Biology
• Trees, Stars, and Multiple Biological Sequence Alignment

Cited in

(6)

• General space-efficient sampling algorithm for suboptimal alignment
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Finding a length-constrained maximum-density path in a tree
• Enumerating \(K\) best paths in length order in DAGs
• A versatile divide and conquer technique for optimal string alignment
• Computing alignments with maximum synchronous moves via replay in coordinate planes

This page was built for publication: On computing all suboptimal alignments

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