A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices

Abstract : Given two strings of size n over a constant alphabet, the classical algorithm for computing the similarity between two sequences [D. Sankoff and J. B. Kruskal, eds., Time Warps, String Edits, and Macromolecules; Addison-Wesley, Reading, MA, 1983; T. F. Smith and M. S. Waterman, J. Molec. Biol., 147 (1981), pp. 195-197] uses a dynamic programming matrix and compares the two strings in O(n²) time. We address the challenge of computing the similarity of two strings in subquadratic time for metrics which use a scoring matrix of unrestricted weights. Our algorithm applies to both local and global similarity computations. The speed-up is achieved by dividing the dynamic programming matrix into variable sized blocks, as induced by Lempel-Ziv parsing of both strings, and utilizing the inherent periodic nature of both strings. This leads to an O(n² / log n) algorithm for an input of constant alphabet size. For most texts, the time complexity is actually O(h n² / log n), where h≤1 is the entropy of the text. We also present an algorithm for comparing two run-length encoded strings of length m and n, compressed into m' and n' runs, respectively, in O(m'n+n'm) complexity. This result extends to all distance or similarity scoring schemes that use an additive gap penalty.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619573
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, March 20, 2013 - 6:50:54 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:02 PM
Long-term archiving on : Friday, June 21, 2013 - 2:45:12 AM

File

02-CLU-TR.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Maxime Crochemore, Gad M. Landau, Michal Ziv-Ukelson. A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2003, 32 (6), pp.1654-1673. ⟨10.1137/S0097539702402007⟩. ⟨hal-00619573⟩

Share

Metrics

Record views

336

Files downloads

297