0

( b、c、a )の形式のトリプレットのデータセットが与えられた場合に、系統樹 (葉ノード内のすべてのデータ) を作成する短いプログラムを作成するタスクが与えられました。ここで、aは最も一般的な祖先です。bとcの。

Aho、Sagiv、Szymanski、および Ullman の論文「Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions」(SIAM J. Computing vol 10 no. 3、1981 年 8 月) のコピーを持っています。アルゴリズムの説明は途中までですが、葉が共通の祖先によって選択される「誘導」というラベルの付いた部分に行き詰まっています。オンラインで情報を探すと、この部分をスキップする傾向があるページが見つかります。私はそれが明らかだと思います、そして私は何かが欠けていますか？

私がこれまでに持っているもの（perlでは、まだサブルーチンに分割されていません）：

use strict;
use warnings;
use Graph; 
use Tree::DAG_NODE;

my @triplets;
while (<>) {
    push @triplets, [ split ];
}

#
# In order to generate the G(L) extract the first two
# columns(edges) of @triplets to make the edges of the auxiliary
# graph. Then pass this array of edges to the Graph constructor.
#
my @auxiliary_edges = map { [@$_[0,1]] } @triplets;

my $graph = Graph->new(
    undirected => 1,
    edges => \@auxiliary_edges
);

my @components = $auxiliary_graph->connected_components;

die "No Tree!" if (@components == 1);     # No tree!

my $root = Tree::DAG_Node->new;
$root->name('_ROOT');

#
# Each connected component is a set of leaves.
#
for my $component (@components)
{
    print "Component (leaf set): [", join(", ", @$component), "]\n";

    #
    # To be written: induced(), which is the heart of my problem,
    # and add_phylo_tree(), which isn't.
    #
    my @matches = induced(\@triplets, $component);
    add_phylo_tree($root, @matches);
}

print_tree($root);    # To be written. I'm using Data::Dumper right now.
exit(0);

データファイル：

b c a
a c d
d e b

検索 ( https://www.google.com/search?q=phylogenetic+tree+from+tripletsが一般的) では、これまでのところ有用な情報は得られませんでしたが、Triplet Methods (PDF) はそれに近づきました (間違いがあるのではないかと思います)。グラフではありますが）。

また、Snir と Rao による「Using Max Cut to Enhance Rooted Trees Consistency」、IEEE/ACM Transactions on Computational Biology and Bioinformatics、vol 3 no. も読みました。4 Oct-Dec 2006)、いくつかの問題を明確にするのに役立ちましたが、私を妨げている問題は解決しませんでした。

ありがとうございました。

4

0 に答える 0