An almost quadratic time algorithm for sparse spliced alignment

DOI10.1007/S00224-009-9239-XMaRDI QIDQ2429729zbMATH OpenOpenAlexFDO

Authors Yoshifumi Sakai

Publication date 1 April 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-009-9239-x

zbMATH Keywords

semi-local string comparisonstring algorithmcommon substring alignment

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Protein sequences, DNA sequences (92D20) Dynamic programming (90C39) Algorithms on strings (68W32)

Recommendations

• Combinatorial Pattern Matching
• Publication:4886031
• scientific article; zbMATH DE number 432798
• Sparse dynamic programming II
• Linear-space algorithms that build local alignments from fragments

Cites work

• scientific article; zbMATH DE number 5158495 (Why is no real title available?)
• A fast algorithm for multiplying min-sum permutations
• A linear-time algorithm for a special case of disjoint set union
• Algorithms on Strings, Trees and Sequences
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Combinatorial Pattern Matching
• On the common substring alignment problem
• Semi-local longest common subsequences in subquadratic time
• Semi-local string comparison: algorithmic techniques and applications

Cited in

(6)

• A data structure for substring-substring LCS length queries
• Dynamic edit distance table under a general weighted cost function
• Computing longest common square subsequences
• scientific article; zbMATH DE number 2087038 (Why is no real title available?)
• A substring-substring LCS data structure
• On almost Monge all scores matrices

This page was built for publication: An almost quadratic time algorithm for sparse spliced alignment

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