An almost quadratic time algorithm for sparse spliced alignment

DOI10.1007/s00224-009-9239-xzbMath1209.68703OpenAlexW2060817260MaRDI QIDQ2429729

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) Dynamic programming (90C39) Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Related Items

A substring-substring LCS data structure ⋮ Dynamic edit distance table under a general weighted cost function ⋮ On almost Monge all scores matrices ⋮ Unnamed Item ⋮ A data structure for substring-substring LCS length queries

Cites Work

• Unnamed Item
• A fast algorithm for multiplying min-sum permutations
• Semi-local string comparison: algorithmic techniques and applications
• Semi-local longest common subsequences in subquadratic time
• A linear-time algorithm for a special case of disjoint set union
• On the Common Substring Alignment Problem
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Algorithms on Strings, Trees and Sequences
• Combinatorial Pattern Matching

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