title: An efficient algorithm for local sequence alignment.
abstract: DNA pairwise sequence alignment has been a subject of great interest in the past and still evokes large interest. Recent algorithms have either been slow and sensitive or fast and less sensitive. Here, we present a new algorithm which is fast and at the same time relatively sensitive. To increase the speed, we first build a suffix tree for both sequences and the alignment is triggered by the maximum matching substring. The algorithm employs mismatch seeds to increase both sensitivity and speed in the later stages. We tested our algorithm on randomly generated sequences of length up to 500 thousand and used Rosetta dataset to test the sensitivity of the algorithm.
authors.affiliation: Computer Science Program, University of Northern British Columbia, Canada, V2N 4Z9.
authors.forename: Waqar
authors.initials: W
authors.lastname: Haque
authors.forename: Alex
authors.initials: A
authors.lastname: Aravind
authors.forename: Bharath
authors.initials: B
authors.lastname: Reddy
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D012984:Software