External Memory Best-First Search for Multiple Sequence Alignment

Matthew Hatem, Wheeler RumlAAAI 2013 · DOI

Abstract

Multiple Sequence Alignment (MSA) is a critical task in computational biology, often modeled as finding the shortest path in a $k$-dimensional lattice. However, optimal search algorithms like A face severe memory constraints, particularly when using biologically accurate affine gap costs which expand the state space significantly. This paper presents PE2A (Parallel External Partial Expansion A), a novel search algorithm that utilizes external storage and parallel processing to handle massive state spaces. PE2A is the first algorithm to successfully solve the entire BAliBASE Reference Set 1 benchmark using affine gap costs, demonstrating superior performance and scalability compared to traditional in-memory and iterative deepening approaches.

Introduction

Multiple Sequence Alignment (MSA) is essential for identifying evolutionary relationships and functional similarities between DNA or protein sequences. Mathematically, the problem involves finding the optimal path through a $k$-dimensional lattice, where $k$ represents the number of sequences.

MSA modeled as a shortest path problem in a lattice with a corresponding score matrix.

While A is the standard for finding shortest paths, its memory requirements are prohibitive for complex MSA problems. The use of affine gap costs, which distinguish between opening and extending gaps, more accurately models biological mutations but increases the state space by a factor of $2^k$. Standard A quickly exhausts RAM by storing all visited and frontier nodes. Previous alternatives, such as Iterative Deepening, often suffer from excessive re-computation or inefficient search orders.

Methods

PE2A* addresses these challenges by integrating three core techniques:

  1. Partial Expansion A (PEA): This method reduces the memory footprint of the "open list" by generating and storing only the most promising successor nodes in RAM, deferring others for later exploration.
  2. Hash-Based Delayed Duplicate Detection (HBDDD): When RAM is exhausted, nodes are partitioned into "buckets" on disk using a hash function. Duplicate detection is performed during a merge phase, where one bucket is processed in RAM at a time.
  3. Parallelization: To overcome disk I/O latency, the algorithm distributes buckets across multiple processors and physical disks, allowing for concurrent processing and data retrieval.

By maintaining a "best-first" search order while utilizing disk space for the search frontier, PE2A* achieves high efficiency without being strictly bound by RAM capacity.

Results

The algorithm was evaluated using the 15-Puzzle baseline and the BAliBASE Reference Set 1 benchmark, which consists of 82 protein sequence instances. These instances are known for being highly dissimilar, representing a challenging "worst-case" for alignment.

Comparative performance metrics for various search algorithms, highlighting PE2A*'s efficiency in time and node generation.

PE2A successfully solved all 82 BAliBASE instances with affine gap costs. Notably, it solved the most difficult instances in under 10 days on a single machine, whereas previous external memory methods like IDDP took 182 hours for just one such instance. On easier instances, PE2A was approximately 1.8x faster than the best in-memory version of PEA, despite the disk overhead. Furthermore, PEA reduced node generation by a factor of 11.8 compared to standard A*, validating the effectiveness of partial expansion in high-branching factor environments.

Conclusion

PE2A* represents a significant advancement in MSA, proving that external memory best-first search can solve problems previously considered intractable due to memory limits. The combination of partial expansion, delayed duplicate detection, and parallelization provides a scalable framework for large-scale biological sequence analysis. Future work will explore the integration of Structured Duplicate Detection (SDD) to further optimize disk I/O and enhance search speed.

Summary updated

BibTeX
@inproceedings{hatem2013external,
  author = {Matthew Hatem and Wheeler Ruml},
  title = {{External Memory Best-First Search for Multiple Sequence Alignment}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8626},
}
Figure