A more efficient algorithm for MPR problems in phylogeny |
| |
Authors: | Hiroshi Narushima and Masazumi Hanazawa |
| |
Institution: | Department of Mathematical Sciences, Tokai University, Hiratsuka 259-12, Japan |
| |
Abstract: | A discrete optimization problem of assigning linearly ordered character-states to the hypothetical ancestors of an evolutionary tree under the principle of maximum parsimony has been discussed. Under the transformation relation of linearly ordered character-states, Farris (1970) and Swofford and Maddison (1987) have dealt with the problem on completely bifurcating phylogenetic trees and presented a solution. Hanazawa et al. (1995) have mathematically formulated the problem with its generalization to any tree and called it the MPR (most-parsimonious reconstruction) problem. Then they have presented clear algorithms for the MPR problem and the related problems. We present a more efficient algorithm for one of the problems, the problem of obtaining the MPR sets. The complexity of the previous algorithm for this problem is O(n2) for the number n of nodes in a given tree, but that of the new algorithm is O(n). |
| |
Keywords: | Evolutionary tree Maximum parsimony Character-state optimization Most-parsimonious reconstruction set Linear algorithm |
本文献已被 ScienceDirect 等数据库收录! |