External Memory Best-First Search for Multiple Sequence Alignment

mhatem and ruml at cs.unh.edu Multiple sequence alignment (MSA) is a central problem in computational biology. It is well known that MSA can be for-mulated as a shortest path problem and solved using heuristic search, but the memory requirement of A * makes it imprac-tical for all but the smallest problems. Partial Expansion A* (PEA*) reduces the memory requirement of A * by generat-ing only the most promising successor nodes. However, even PEA * exhausts available memory on many problems. An-other alternative is Iterative Deepening Dynamic Program-ming, which uses an uninformed search order but stores only the nodes along the search frontier. However, it too can-not scale to the largest problems. In this paper, we propose storing nodes on cheap and plentiful secondary storage. We present a new general-purpose algorithm, Parallel External PEA * (PE2A*), that combines PEA * with Delayed Duplicate Detection to take advantage of external memory and multiple processors to solve large MSA problems. In our experiments, PE2A * is the first algorithm capable of solving the entire Ref-erence Set 1 of the standard BAliBASE benchmark using a biologically accurate cost function. This work suggests that external best-first search can effectively use heuristic infor-mation to surpass methods that rely on uninformed search or-ders