進化木のQuarted distance の計算アルゴリズムの実装

• Item type: SIG Technical Reports(1)
• 公開日: 2003-05-23
• タイトル: 進化木のQuarted distance の計算アルゴリズムの実装
• タイトル / 言語: en
• タイトル: Research on Algorithm Computing the Quartet Distance between Evolutional Trees
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): GSIS, Tohoku University
• 著者所属(英): en
• 著者所属(英): GSIS, Tohoku University
• 著者名: 廣川, 裕; 徳山, 豪
• 著者名(英): Yutaka, Hirokawa; Takeshi, Tokuyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 生物進化学においては種と種の関係を表す進化木が中心的な道具となっており、異なった進化木同士の違いを定量化することはとても重要な仕事である。quartet distanceとは、Estabrook McMorris Meachamらによって提案された二つの木の間の距離尺度である。生物種のうち4種を選択することによって得られる部分木の組み合わせ構造をquartet topologyというが、二つの根を持たない進化木の間で異なったquartet topologyを取る4種の組み合わせの数をquartet distanceと言う。本研究ではBrodal他が2001年に発表したquartet distanceをO(nlog^2(n))の時間で計算するプログラムを実装し、実験結果を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In evolutionary biology, evolutionary trees describing the relationship of a set of spieces are widely used, and quantifying differences between evolutional trees is a weighty task. The quartet distance is a distance measure between trees proposed by Estabrook, McMorris and Meacham. In this paper, we report experimental results on the algorithm put up by G.S.Brodal et al. in 2001, which compute the quartet distance between two unrooted evolutionary trees of n species in time O(nlog^2(n)).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2003, 号 53(2003-AL-090), p. 1-8, 発行日 2003-05-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会