A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost MatricesReportar como inadecuado

A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost Matrices - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

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

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


Documentos relacionados