Research Articles A Geometric Interpretation for Local Alignment-Free Sequence Comparison

Local alignment-free sequence comparison arises in the context of identifying similar seg-ments of sequences that may not be alignable in the traditional sense. We propose a ran-domized approximation algorithm that is both accurate and efficient. We show that under D2 and its important variant D 2 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 align-ment-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. There-fore, 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. Key words: algorithms, alignment, dynamic programming, metagenomics. 1