分岐学における祖先推定: 組合せ最適化問題としての系統推定 Ancestral reconstruction in cladistics : phylogeny estimation as a combinatorial optimization problem

この論文にアクセスする

この論文をさがす

著者

抄録

生物の形質状態データを与えたとき,系統関係を最節約的に推定するという基準を置く.このとき分岐図 (系統樹) の内部分岐点 (仮想的共通祖先) に配置できる仮想的形質状態 (PR : 最節約形質復沼を網羅的に枚挙することは,形質進化の歴史を復元する際には不可欠である.この問題は、離散数学的にはSteiner tree問題の一部である、Steiner点の構築と枚挙という離散的最適化問題に関係する。しかし,あるOTU形質データのもとでのMPR集合 (同程度に最節約的なMPRの全体集合) を網羅するだけでは,形質進化の解析を進める上では不十分である.個々のMPRの特性,相異なるMPR間の比較方法モしてMPRの背後にある生物学的仮定を明らかにする必要がある.ここではMPR集合の代数的性質を解析し,MPR間の構造比較をするための一つの規準として提出した歪み指数 (istortion inde) について述べる.歪み指数は,分岐図の根に対して決定される部分木があるMPRのもとで持つ全長と基準MPR (CCTRA) との偏差 (正の値) を全部分木に関して合計することにより得られる.ACCTRANの歪み指数はゼロである.したがって,ACCTRANではないすべてのMPRはある正の歪み指数を持つことになる.歪み指数は,特定の部分本に形質進化がどの程度集中しているかの尺度を与える.歪み指数から見ると,ACCTRANではすべての部分本に均等に形質進化が分散しているのに対し.DELTRANでは特定の部分木に形質進化が集中しているといえる.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") can 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 all 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, while my 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.

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.

収録刊行物

  • 情報処理学会研究報告数理モデル化と問題解決(MPS)

    情報処理学会研究報告数理モデル化と問題解決(MPS) 1997(41(1997-MPS-013)), 7-12, 1997-05-15

    一般社団法人情報処理学会

参考文献:  29件中 1-29件 を表示

各種コード

  • NII論文ID(NAID)
    110002936265
  • NII書誌ID(NCID)
    AN10505667
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • データ提供元
    CJP書誌  NII-ELS  IPSJ 
ページトップへ