LISP and Symbolic Computation, 7(2/3)211-229
An Application of an OR-Parallel Prolog Systemto Phylogenetic AnalysisHideo Matsuda, Department of Computer and Systems Engineering, Faculty of Engineering, Kobe University, 1-1 Rokkodai, Nada, Kobe 657, Japan
Yukio Kaneda, Department of Computer and Systems Engineering, Faculty of Engineering, Kobe University, 1-1 Rokkodai, Nada, Kobe 657, Japan
|
Abstract: In this paper we discuss an application of our
OR-Parallel Prolog system to a search problem of importance in
practice: the construction of phylogenetic trees. The use of a maximum
likelihood method to construct such trees is based on concrete models
of evolutional processes and is well-motivated statistically. However,
the use of maximum likelihood methods has been hindered by the
computational cost to calculate the likelihood of possible alternative
trees (i.e. their confidence scores) at each search step for the
optimal tree. To cope with this problem, we used OR-parallel Prolog as
a "coordination language" to orchestrate the search for the optimal
tree. A numerical computation written in C computed the likelihood of
each alternative tree and a symbolic computation written in Prolog
performed a parallel A* tree search. For constructing phylogenetic
trees of bacterial organisms, our parallel algorithm allowed us to
increase the size of the search space, allowing us to include nearly
optimal as well as optimal intermediate trees in the search. Our
priority mechanism reduced the generation of useless tasks and
resulted in superlinear speedups in some cases. Keywords: logic programming, Prolog, OR-parallelism, search algorithm, phylogenetic analysis |
This article is not available online.
![[picture of journal cover]](../LISP.JPG)