A time-efficient, linar-space local similarity algorithm

DOI10.1016/0196-8858(91)90017-DzbMath0748.90079WikidataQ107138276 ScholiaQ107138276MaRDI QIDQ1189709

Webb Miller, Xiaoqiu Huang

Publication date: 27 September 1992

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

biosequence datalocal alignments

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39) Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (12)

Sensitivity analysis and efficient method for identifying optimal spaced seeds ⋮ Efficient bottom-up hybrid hierarchical clustering techniques for protein sequence classification ⋮ Linear-space algorithms that build local alignments from fragments ⋮ The ribosome as a missing link in the evolution of life ⋮ Block edit models for approximate string matching ⋮ Computing similarity of run-length encoded strings with affine gap penalty ⋮ APPROXIMATION ALGORITHMS FOR LOCAL ALIGNMENT WITH LENGTH CONSTRAINTS ⋮ Constrained sequence alignment ⋮ Local multiple alignment via subgraph enumeration ⋮ Elucidating the protein cold-adaptation: investigation of the parameters enhancing protein psychrophilicity ⋮ On spaced seeds for similarity search ⋮ A technique to find multiple motif occurrences in a biomolecular sequence

Cites Work

• Pattern recognition in genetic sequences by mismatch density
• Approximate matching of regular expressions
• On the computational power of pushdown automata
• Self-adjusting binary search trees
• The theory and computation of evolutionary distances: Pattern recognition
• A linear space algorithm for computing maximal common subsequences
• Unnamed Item

This page was built for publication: A time-efficient, linar-space local similarity algorithm