ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases
Summary: ALAE accelerates exact Smith–Waterman local alignment with affine gaps via a compressed suffix array, preserving completeness unlike BLAST. Filtering and score reuse prune and recycle BWT-SW computations, yielding subquadratic bounds and substantial speedups, especially for long queries. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Xiaochun Yang (Northeastern University)
- 2. Honglei Liu (Northeastern University)
- 3. Bin Wang (Northeastern University)
BibTeX Citation
@article{yang_vldb12,
title = {{ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases}},
author = {Yang, Xiaochun and Liu, Honglei and Wang, Bin},
journal = {PVLDB},
series = {{VLDB} '12},
volume = {5},
number = {11},
pages = {1507--1518},
doi = {10.14778/2350229.2350250},
url = {https://doi.org/10.14778/2350229.2350250},
year = {2012}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,071 | Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints | 2020 | VLDB | 6.3761034e-05 |
| 5,726 | Pigeonring: A Principle for Faster Thresholded Similarity Search | 2019 | VLDB | 6.1079184e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,164 | OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences | 2003 | VLDB | 7.6778551e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 12,297 | RACE: A Scalable and Elastic Parallel System for Discovering Repeats in Very Long Sequences | 2013 | VLDB |
| 2 | 7,692 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD |
| 3 | 10,086 | Efficient and Effective KNN Sequence Search with Approximate n-grams | 2014 | VLDB |
| 4 | 13,474 | On the String Matching with k Differences in DNA Databases | 2021 | VLDB |
| 5 | 10,265 | LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH | 2026 | SIGMOD |
| 6 | 7,676 | Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts | 2021 | SIGMOD |
| 7 | 12,558 | Improving Suffix Array Locality for Fast Pattern Matching on Disk | 2008 | SIGMOD |
| 8 | 6,496 | Reference-Based Indexing of Sequence Databases | 2006 | VLDB |
| 9 | 3,164 | OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences | 2003 | VLDB |
| 10 | 6,182 | Reference-Based Alignment in Large Sequence Databases | 2009 | VLDB |