Sparse Normalized Local Alignment |
| |
Authors: | Nadav Efraty Gad M Landau |
| |
Affiliation: | (1) Department of Computer Science, University of Haifa, Haifa 31905, Israel;(2) Department of Computer and Information Science, Polytechnic University, Six MetroTech Center, Brooklyn, NY 11201-3840, USA |
| |
Abstract: | Given two strings, X and Y, both of length O(n) over alphabet
Σ, a basic problem (local alignment) is to find pairs
of similar substrings, one from X and one from Y. For
substrings X' and Y' from X and Y, respectively, the
metric we use to measure their similarity is normalized
alignment value: LCS(X',Y')/(|X'|+|Y'|). Given an integer M
we consider only those substrings whose LCS length is at least
M. We present an algorithm that reports the pairs of substrings
with the highest normalized alignment value in
O(n log|Σ|+rM log log n) time (r—the number of
matches between X and Y). We also present an
O(n log|Σ|+rL log log n) algorithm (L = LCS(X,Y)) that
reports all substring pairs with a normalized alignment value
above a given threshold. |
| |
Keywords: | Algorithms String matching Dynamic programming Local alignment Largest Common Subsequence (LCS) |
本文献已被 SpringerLink 等数据库收录! |
|