A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost MatricesReport as inadecuate

A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost Matrices - Download this document for free, or read online. Document in PDF available to download.

1 LIGM - Laboratoire d-Informatique Gaspard-Monge 2 University of Haifa Haifa

Abstract : The classical algorithm for computing the similarity between two sequences 36, 39 uses a dynamic programming matrix, and compares two strings of size n in On² time. We address the challenge of computing the similarity of two strings in sub-quadratic time, for metrics which use a scoring matrix of unrestricted weights. Our algorithm applies to both local and global alignment 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 On²-log n algorithm for an input of constant alphabet size. For most texts, the time complexity is actually Ohn²-log n where h ≤ 1 is the entropy of the text.

Author: Maxime Crochemore - Gad M. Landau - Michal Ziv-Ukelson -

Source: https://hal.archives-ouvertes.fr/


Related documents