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.
|主出版物標題||Advances in Software Engineering|
|主出版物子標題||International Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers|
|編輯||Tai-hoon Kim, Wai Chi Fang, Changhoon Lee, Kirk P. Arnett|
|出版狀態||Published - 2009 十二月 1|
|名字||Communications in Computer and Information Science|
All Science Journal Classification (ASJC) codes