Linear-space algorithms that build local alignments from fragments

DOI10.1007/BF01188583zbMath0840.92010OpenAlexW2042158592MaRDI QIDQ1902469

Webb Miller, Kun-Mao Chao

Publication date: 1 July 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01188583

zbMATH Keywords

DNA sequencessequence comparisonslinear-space algorithmalignment fragmentscandidate-list paradigmlocal alignment algorithmtime-efficient algorithm

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08) Discrete mathematics in relation to computer science (68R99)

Related Items

Local multiple alignment via subgraph enumeration ⋮ On computing all suboptimal alignments ⋮ A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences

Uses Software

• FASTA

Cites Work

• Pattern recognition in genetic sequences by mismatch density
• Sequence comparison with concave weighting functions
• Speeding up dynamic programming with applications to molecular biology
• A time-efficient, linar-space local similarity algorithm
• Dynamic programming with convexity, concavity and sparsity
• An \(O(N^ 2 \log N)\) restriction map comparison and search algorithm
• Constrained sequence alignment
• The Context Dependent Comparison of Biological Sequences
• A linear space algorithm for computing maximal common subsequences
• Sparse dynamic programming I
• Sparse dynamic programming II
• The String-to-String Correction Problem