On computing all suboptimal alignments

DOI10.1016/S0020-0255(97)10032-9zbMath0944.92007OpenAlexW2012143472MaRDI QIDQ1291563

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

sequence comparisondivide-and-conquerlinear-space algorithmminimal directed acyclic graphsuboptimal alignments

Mathematics Subject Classification ID

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

Related Items (3)

Enumerating \(K\) best paths in length order in DAGs ⋮ General space-efficient sampling algorithm for suboptimal alignment ⋮ Finding a length-constrained maximum-density path in a tree

Cites Work

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

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