A time-efficient, linar-space local similarity algorithm

DOI10.1016/0196-8858(91)90017-DMaRDI QIDQ1189709zbMATHWikidataFDO

Authors Xiaoqiu Huang, Webb Miller

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) Protein sequences, DNA sequences (92D20) Dynamic programming (90C39) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Recommendations

• Linear-space algorithms that build local alignments from fragments
• Fast Algorithms for Local Similarity Queries in Two Sequences
• Locally optimal subalignments using nonlinear similarity functions
• scientific article; zbMATH DE number 5171901
• FastLSA: A fast, linear-space, parallel and sequential algorithm for sequence alignment

Cites work

• scientific article; zbMATH DE number 4116362 (Why is no real title available?)
• A linear space algorithm for computing maximal common subsequences
• Approximate matching of regular expressions
• On the computational power of pushdown automata
• Pattern recognition in genetic sequences by mismatch density
• Self-adjusting binary search trees
• The theory and computation of evolutionary distances: Pattern recognition

Cited in

(22)

• Efficient algorithms for local alignment search
• Efficient algorithms for similarity search
• scientific article; zbMATH DE number 2089427 (Why is no real title available?)
• Locally optimal subalignments using nonlinear similarity functions
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• Constrained sequence alignment
• Fast Algorithms for Local Similarity Queries in Two Sequences
• BIT-PARALLEL COMPUTATION OF LOCAL SIMILARITY SCORE MATRICES WITH UNITARY WEIGHTS
• Block edit models for approximate string matching
• The ribosome as a missing link in the evolution of life
• FastLSA: A fast, linear-space, parallel and sequential algorithm for sequence alignment
• Global and local sequence alignment with a bounded number of gaps
• Computing and Combinatorics
• An efficient alignment algorithm for masked sequences
• Linear-space algorithms that build local alignments from fragments
• On spaced seeds for similarity search
• Efficient bottom-up hybrid hierarchical clustering techniques for protein sequence classification
• A technique to find multiple motif occurrences in a biomolecular sequence
• Local multiple alignment via subgraph enumeration
• APPROXIMATION ALGORITHMS FOR LOCAL ALIGNMENT WITH LENGTH CONSTRAINTS
• Elucidating the protein cold-adaptation: investigation of the parameters enhancing protein psychrophilicity
• Computing similarity of run-length encoded strings with affine gap penalty

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

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