A tiling bound for pairwise global sequence alignment

Brice Horton Ii Paul, Martin Frith

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publicationAdvances in Software Engineering
Subtitle of host publicationInternational Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers
EditorsTai-hoon Kim, Wai Chi Fang, Changhoon Lee, Kirk P. Arnett
Number of pages6
Publication statusPublished - 2009 Dec 1

Publication series

NameCommunications in Computer and Information Science
ISSN (Print)1865-0929

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A tiling bound for pairwise global sequence alignment'. Together they form a unique fingerprint.

Cite this