Ancestral reconstruction in cladistics : phylogeny estimation as a combinatorial optimization problem

• MINAKA Nobuhiro

  National Institute of Agro-Environmental Sciences

Bibliographic Information

Other Title

• 分岐学における祖先推定 : 組合せ最適化問題としての系統推定

Abstract

For a given character data set of organisms. reconstructing the character states of the interior points (that is hypothetical common ancestors) on a phylogenetic tree (branching graph) has been recognized as an important combinatorial problem related to the analysis of character evolution. Under the principle of parsimony, this problem is a kind of combinatorial optimization related to the Steiner tree problem, that is, to enumerate all "most parsimonious reconstructions" ("MPRs" as Steiner points) in a tree. The ancestral reconstruction problem poses several interesting problems for discrete mathematicians as well as for systematic biologists. The set of these equally most parsimonious reconstructions ("MPR-space") cam be partially ordered by a binary ordering relation ("MPR partial order"). Several algebraic properties of the solution space ("MPR-poset") are derived from this partial-order formulation. An MPR ("ACCTRAN") exists which minimizes the length of any subtree of the cladogram. I proposed a new index, called "distortion index, " which is defined to be the cumulative difference between the lengths of all subtrees of ACCTRAN and those of other MPRs. Finally, ACCTRAN will not show by definition any distortion in character state changes in the full cladogram, white any non-ACCTRAN shows more or less distortion in some subtree(s). This suggests that, from a biological viewpoint each reconstruction seems to have its own substantial assumption on character evolution.

Journal

• IPSJ SIG Notes

  IPSJ SIG Notes 13 7-12, 1997-05-15

  Information Processing Society of Japan (IPSJ)

Details

• CRID: 1570854177223849344
• NII Article ID: 110002936265
• NII Book ID: AN10505667
• ISSN: 09196072
• Text Lang: ja
• Data Source:
  • CiNii Articles