A Tiling Bound for Pairwise Global Sequence Alignment

Paul Horton & Martin Frith
AIST, Computational Biology Research Center

Proceedings of Bioscience and BioTechnology (BSBT2008), Sānyà, China, December 2008.
Post-proceedings published as: ASEA 2008, CCIS 30:93-98, 2009.

In this paper we motivate the need to develop new techniques to accelerate pairwise global sequence alignment and then propose a tiling bound to achieve this. The bounds involve a problem relaxation in which alignment scores of sequence fragments are combined to give a bound on the distance of any alignment passing through any particular point in the edit graph. We prove the correctness of the bound and briefly discuss possible implementation strategies.