A Tiling Bound for Pairwise Global Sequence Alignment

Abstract. 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