異種系統樹間の調停のためのゼロ交差制約の充足
スポンサーリンク
概要
- 論文の詳細を見る
二つの異種系統樹データベースから解析に必要な二つの部分木を検索し, それらの部分木から一つの調停木を作成することは, 生物種の分子進化学的な研究を行うために有用である. この調停木の作成・利用を効果的に行うために, それらの二つの部分木に対して木の葉節点列がお互いに一致する順序木を見つけることが大変重要である. それらの二つの順序木はゼロ交差制約を満足しており, 木構造同士を比較研究する上で便利な順序づけになっている. 本論文では, 検索された二つの部分木 (異種系統樹) からゼロ交差制約を満足する二つの順序木を探索する方法が提案されている. ゼロ交差制約の充足は, 葉節点列間に結合行列を定義し, その結合行列に対して, あるヒューリスティックを用いた木探索を行うことにより達成されている. この木探索では, 木の枝の間に交差が発生するのを回避するために, 葉節点に関するクラスタを定義し, クラスタ同士の交換に基づいた葉節点列の順序づけを行っている. / After searching two subtrees from two heterogeneous tree databases, a reconciled tree found from two heterogeneous subtrees is useful for understanding biological diversity, researching gene duplications, reconstructing taxonomic trees, and assigning a taxonomic name to each branch node of gene trees. It is very important to find two ordered trees with the same sequence of leaf nodes in order to achieve an effective reconciliation. For the reconciliation, two ordered trees that satisfy the zero-crossover constraint are useful for comparing the two heterogeneous trees. This paper proposes a new method for searching for two orddred trees that satisfy the zero-crossover constraint. This is achieved using a heuristic tree search for an interconnection matrix, which is defined by the leaf sequences (layers) of the two trees. To avoid crossovers between the branches of either tree, the order of each leaf sequence is modified in the tree search. The search orders the leaf sequence using swap operations between two clusters with respect to leaf nodes. The method is implemented in Prolog and the implementation results also are presented.
- 社団法人情報処理学会の論文
- 1999-05-15
社団法人情報処理学会 | 論文
- 5 テーブルトップインタフェース(実世界インタフェースの新たな展開)
- 内部ネットワーク監視を目的とした時間・論理・地理情報の統合的視覚化システム(コンピュータグラフィックス)
- 個人認証システム「あわせ絵」の安全性と利便性に関する評価実験(信頼性,ユビキタス社会を支えるコンピュータセキュリティ技術)
- おはじきインタフェース : ハイスピードカメラを用いた指を弾くジェスチャの認識(入力と表現(1),表現のためのインタフェース,および一般)
- 壁型ディスプレイとの非接触対話手法に関する研究(コミュニケーションと表現,表現のためのインタフェース,および一般)