不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法 Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data

Search this Article

Author(s)

    • 清見 礼 KIYOMI Masashi
    • 横浜市立大学 国際総合科学部 International College of Arts and Sciences, Yokohama City University
    • 岡本 吉央 OKAMOTO Yoshio
    • 電気通信大学 大学院情報理工学研究科 情報・通信工学専攻 Department of Communication Engineering and Informatics, Graduate School of Informatics and Engineering, University of Electro-Communications
    • 斎藤 寿樹 SAITOH Toshiki
    • 神戸大学 大学院工学研究科 電気電子工学専攻 Department of Electrical and Electronic Engineering, Graduate School of Engineering, Kobe University

Abstract

不完全なデータが与えられたときに,形質に基づいて系統樹を復元する問題を研究する.より正確には,形質が二値であり,有向完全系統樹の仮定が成り立つ場合に,ある種に対してある形質の状態がデータとして失われている状況を考える.本研究の目的は失われたデータを補完したときに得られる完全系統樹をすべて列挙するための効率的アルゴリズムを設計することである.単純な分枝限定アルゴリズム(B&B)は理論的に良い計算量を持つが,ゼロサプレス型二分決定グラフ(ZDD)に基づく別の方法を提案する.ランダム生成されたデータに対する実験では,ZDDに基づく手法がB&Bよりも優れた結果を示した.また,与えられた不完全データと矛盾しない完全系統樹の数を計算する問題が#P完全であることを示し,すなわち,効率的標本抽出が難しいことの傍証を与える.

We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B&B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B&B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard. This article is a technical report without peer review, and its polished version will be published elsewhere.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 112(93), 17-24, 2012-06-14

    The Institute of Electronics, Information and Communication Engineers

References:  14

Codes

  • NII Article ID (NAID)
    110009588447
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • Article Type
    ART
  • ISSN
    0913-5685
  • NDL Article ID
    023811077
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top