A tabu search algorithm for maximum parsimony phylogeny inference |
| |
Authors: | Yu-Min Lin Shu-Cherng Fang Jeffrey L Thorne |
| |
Institution: | 1. Department of Industrial Engineering and Operations Research Program, North Carolina State University, Raleigh, NC 27695-7906, USA;2. Departments of Genetics and Statistics, North Carolina State University, Raleigh, NC 27695-7566, USA;3. Departments of Mathematical Sciences and Industrial Engineering, Tsinghua University, Beijing, PR China |
| |
Abstract: | Phylogeny reconstruction is too complex a combinatorial problem for an exhaustive search, because the number of possible solutions increases exponentially with the number of taxa involved. In this paper, we adopt the parsimony principle and design a tabu search algorithm for finding a most parsimonious phylogeny tree. A special array structure is employed to represent the topology of trees and to generate the neighboring trees. We test the proposed tabu search algorithm on randomly selected data sets obtained from nuclear ribosomal DNA sequence data. The experiments show that our algorithm explores fewer trees to reach the optimal one than the commonly used program “dnapenny” (branch-and-bound based) while it generates much more accurate results than the default options of the program “dnapars” (heuristic search based). The percentage of search space needed to find the best solution for our algorithm decreased rapidly as the number of taxa increased. For a 20-taxon phylogeny problem, it needs on average to examine only 3.92 × 10−15% of the sample space. |
| |
Keywords: | Tabu search OR in biology Bioinformatics Phylogeny inference Maximum parsimony |
本文献已被 ScienceDirect 等数据库收录! |
|