On computing all suboptimal alignments
From MaRDI portal
Publication:1291563
DOI10.1016/S0020-0255(97)10032-9zbMath0944.92007MaRDI QIDQ1291563
Publication date: 20 September 2000
Published in: Information Sciences (Search for Journal in Brave)
sequence comparison; divide-and-conquer; linear-space algorithm; minimal directed acyclic graph; suboptimal alignments
90C90: Applications of mathematical programming
90C39: Dynamic programming
92C40: Biochemistry, molecular biology
68W10: Parallel algorithms in computer science
92-08: Computational methods for problems pertaining to biology
Related Items
Finding a length-constrained maximum-density path in a tree, Enumerating \(K\) best paths in length order in DAGs, General space-efficient sampling algorithm for suboptimal alignment
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
