title: A geometric interpretation for local alignment-free sequence comparison.
abstract: Local alignment-free sequence comparison arises in the context of identifying similar segments of sequences that may not be alignable in the traditional sense. We propose a randomized approximation algorithm that is both accurate and efficient. We show that under D2 and its important variant [Formula: see text] as the similarity measure, local alignment-free comparison between a pair of sequences can be formulated as the problem of finding the maximum bichromatic dot product between two sets of points in high dimensions. We introduce a geometric framework that reduces this problem to that of finding the bichromatic closest pair (BCP), allowing the properties of the underlying metric to be leveraged. Local alignment-free sequence comparison can be solved by making a quadratic number of alignment-free substring comparisons. We show both theoretically and through empirical results on simulated data that our approximation algorithm requires a subquadratic number of such comparisons and trades only a small amount of accuracy to achieve this efficiency. Therefore, our algorithm can extend the current usage of alignment-free-based methods and can also be regarded as a substitute for local alignment algorithms in many biological studies.
authors.affiliation: Molecular and Computational Biology, University of Southern California, Los Angeles, California 90089-2910, USA.
authors.forename: Ehsan
authors.initials: E
authors.lastname: Behnam
authors.forename: Michael S
authors.initials: MS
authors.lastname: Waterman
authors.forename: Andrew D
authors.initials: AD
authors.lastname: Smith
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D006801:Humans; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software