A more efficient algorithm for MPR problems in phylogeny

✍ Scribed by Hiroshi Narushima; Masazumi Hanazawa

• Book ID: 104294835
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 497 KB
• Volume: 80
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00088-7

✦ Synopsis

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 have dealt with the problem on completely bifurcating phylogenetic trees and presented a solution. Hanazawa et al. (199.5) 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(n') for the number n of nodes in a given tree, but that of the new algorithm is O(n).