A tiling bound for pairwise global sequence alignment

Brice Horton Ii Paul; Martin Frith

doi:10.1007/978-3-642-10242-4_8

A tiling bound for pairwise global sequence alignment

Brice Horton Ii Paul, Martin Frith

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Advances in Software Engineering
Subtitle of host publication	International Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers
Editors	Tai-hoon Kim, Wai Chi Fang, Changhoon Lee, Kirk P. Arnett
Pages	93-98
Number of pages	6
DOIs	https://doi.org/10.1007/978-3-642-10242-4_8
Publication status	Published - 2009 Dec 1

Publication series

Name	Communications in Computer and Information Science
Volume	30
ISSN (Print)	1865-0929

All Science Journal Classification (ASJC) codes

Computer Science(all)
Mathematics(all)

Access to Document

10.1007/978-3-642-10242-4_8

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

Cite this

Paul, B. H. I., & Frith, M. (2009). A tiling bound for pairwise global sequence alignment. In T. Kim, W. C. Fang, C. Lee, & K. P. Arnett (Eds.), Advances in Software Engineering: International Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers (pp. 93-98). (Communications in Computer and Information Science; Vol. 30). https://doi.org/10.1007/978-3-642-10242-4_8

Paul, Brice Horton Ii ; Frith, Martin. / A tiling bound for pairwise global sequence alignment. Advances in Software Engineering: International Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers. editor / Tai-hoon Kim ; Wai Chi Fang ; Changhoon Lee ; Kirk P. Arnett. 2009. pp. 93-98 (Communications in Computer and Information Science).

@inproceedings{8deca45054c84412a03a40726294e496,

title = "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.",

author = "Paul, {Brice Horton Ii} and Martin Frith",

year = "2009",

month = dec,

day = "1",

doi = "10.1007/978-3-642-10242-4_8",

language = "English",

isbn = "9783642102417",

series = "Communications in Computer and Information Science",

pages = "93--98",

editor = "Tai-hoon Kim and Fang, {Wai Chi} and Changhoon Lee and Arnett, {Kirk P.}",

booktitle = "Advances in Software Engineering",

}

Paul, BHI & Frith, M 2009, A tiling bound for pairwise global sequence alignment. in T Kim, WC Fang, C Lee & KP Arnett (eds), Advances in Software Engineering: International Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers. Communications in Computer and Information Science, vol. 30, pp. 93-98. https://doi.org/10.1007/978-3-642-10242-4_8

A tiling bound for pairwise global sequence alignment. / Paul, Brice Horton Ii; Frith, Martin.

Advances in Software Engineering: International Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers. ed. / Tai-hoon Kim; Wai Chi Fang; Changhoon Lee; Kirk P. Arnett. 2009. p. 93-98 (Communications in Computer and Information Science; Vol. 30).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A tiling bound for pairwise global sequence alignment

AU - Paul, Brice Horton Ii

AU - Frith, Martin

PY - 2009/12/1

Y1 - 2009/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=73349108415&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=73349108415&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10242-4_8

DO - 10.1007/978-3-642-10242-4_8

M3 - Conference contribution

AN - SCOPUS:73349108415

SN - 9783642102417

T3 - Communications in Computer and Information Science

SP - 93

EP - 98

BT - Advances in Software Engineering

A2 - Kim, Tai-hoon

A2 - Fang, Wai Chi

A2 - Lee, Changhoon

A2 - Arnett, Kirk P.

ER -

Paul BHI, Frith M. A tiling bound for pairwise global sequence alignment. In Kim T, Fang WC, Lee C, Arnett KP, editors, Advances in Software Engineering: International Conference, ASEA 2008, and Its Special Sessions, Sanya, Hainan Island, China, December 13-15, 2008. Revised Selected Papers. 2009. p. 93-98. (Communications in Computer and Information Science). https://doi.org/10.1007/978-3-642-10242-4_8