{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:07:35Z","timestamp":1758272855206},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"\n We study the problem of local alignment, which is finding pairs of similar subsequences with gaps. The problem exists in biosequence databases. BLAST is a typical software for finding local alignment based on heuristic, but could miss results. Using the Smith-Waterman algorithm, we can find all local alignments in O(\n mn<\/jats:italic>\n ) time, where\n m<\/jats:italic>\n and\n n<\/jats:italic>\n are lengths of a query and a text, respectively. A recent exact approach BWT-SW improves the complexity of the Smith-Waterman algorithm under constraints, but still much slower than BLAST. This paper takes on the challenge of designing an accurate and efficient algorithm for evaluating local-alignment searches, especially for long queries. In this paper, we propose an efficient software called ALAE to speed up BWT-SW using a compressed suffix array. ALAE utilizes a family of filtering techniques to prune meaningless calculations and an algorithm for reusing score calculations. We also give a mathematical analysis and show that the upper bound of the total number of calculated entries using ALAE could vary from 4.50\n mn<\/jats:italic>\n 0.520<\/jats:sup>\n to 9.05\n mn<\/jats:italic>\n 0.896<\/jats:sup>\n for random DNA sequences and vary from 8.28\n mn<\/jats:italic>\n 0.364<\/jats:sup>\n to 7.49\n mn<\/jats:italic>\n 0.723<\/jats:sup>\n for random protein sequences. We demonstrate the significant performance improvement of ALAE on BWT-SW using a thorough experimental study on real biosequences. ALAE guarantees correctness and accelerates BLAST for most of parameters.\n <\/jats:p>","DOI":"10.14778\/2350229.2350265","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1507-1518","source":"Crossref","is-referenced-by-count":4,"title":["ALAE"],"prefix":"10.14778","volume":"5","author":[{"given":"Xiaochun","family":"Yang","sequence":"first","affiliation":[{"name":"Northeastern University, Liaoning China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Honglei","family":"Liu","sequence":"additional","affiliation":[{"name":"Northeastern University, Liaoning China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Wang","sequence":"additional","affiliation":[{"name":"Northeastern University, Liaoning China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/25.17.3389"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024694.1024701"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796543"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_7_1","first-page":"73","article-title":"Use of long sequence alignments to study the evolution and regulation of mammalian globin gene clusters","volume":"10","author":"Hardison R.","year":"1993","unstructured":"R. Hardison and W. Miller . Use of long sequence alignments to study the evolution and regulation of mammalian globin gene clusters . Mol Biol Evol. , 10 : 73 -- 102 , 1993 . R. Hardison and W. Miller. Use of long sequence alignments to study the evolution and regulation of mammalian globin gene clusters. Mol Biol Evol., 10:73--102, 1993.","journal-title":"Mol Biol Evol."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn032"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp698"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_11_1","first-page":"910","volume-title":"VLDB","author":"Meek C.","year":"2003","unstructured":"C. Meek , J. M. Patel , and S. Kasetty . OASIS: An online and accurate technique for local-alignment searches on biological sequences . In VLDB , pages 910 -- 921 , 2003 . C. Meek, J. M. Patel, and S. Kasetty. OASIS: An online and accurate technique for local-alignment searches on biological sequences. In VLDB, pages 910--921, 2003."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.809403"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.204"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:29:46Z","timestamp":1672226986000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350265"}},"subtitle":["accelerating local alignment with affine gap exactly in biosequence databases"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":13,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350265"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350265","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}