2

私は最近、系統樹を推測するための数学的および計算方法に関する素晴らしい本である Joseph Felsenstein によるInferring Phylogeniesを購入し、そこに記述されているアルゴリズムのいくつかを実装して遊んでいます。

具体的には、永続的なデータ構造を備えた機能的な設定で使用することに興味があります。多くの方法では、可能なツリーのスペースを歩く必要があり、構造を介して行ってきた場所の履歴を安価に覚えておくとよいでしょう。共有 (このブログ投稿の「ワールド」で aphyr が行うことのようなもの)、以前に計算されたサブツリーの値を簡単にキャッシュするなど。

これに関する問題は、多くの方法がツリーの「ルート変更」を伴うことであり、純粋に機能的な方法で安価に行う方法がわかりません。基本的に、次のそれぞれのアイデアをキャプチャする何らかの方法が必要です (ツリーをベクトルとして表す clojure 表記法を使用):

[:a [:b [:c :d]]] 
[:b [:a [:c :d]]]
[:a [:b [:d :c]]]
[:b [:a [:d :c]]]
[[:a :b] [:c :d]] 
[[:c :d] [:a :b]]
[:c [:d [:a :b]]]
[:d [:c [:a :b]]]
[:c [:d [:b :a]]]
[:d [:c [:b :a]]]

同じデータを表し、ルートが配置されている場所のみが異なります。それらはそれぞれ根のないツリーを表します。

a   b
 \ /
  |
 / \
c   d

これらのツリーの 1 つにジッパーで移動してから関数を呼び出すとreroot、ルートが現在の になるように圧縮された新しいツリーが返されlocます。

Felsenstein という本の中で、低コストでルートを変更できるツリーのデータ構造について説明しています。

ひどい図

円は構造体で、矢印はポインタです。構造体のリングはツリーの内部ノードであり、構造体への参照を取得したら、ポインターの交換を行うことでルートをそこに移動できます。残念ながら、これは変更操作であり、相互参照が必要ですが、どちらも純粋に機能的な設定では不可能です。

ジッパーを使ってやりたいことをする方法があるはずだと思いますがclojure.core/zip、しばらくいじっていて、どこにも行きません.

このようなものの実装を知っている人はいますか、または私が読むべきこと/私が見るべき論文/これを行う方法についてのアイデアについての提案はありますか?

ありがとう！

4

2 に答える 2

2

jvm は、直接操作できるようなポインタへのアクセスを実際には提供しません。しかし、二重結合構造を表現するためのいくつかのオプションがあります。

これはグラフによく似ており、このようなまばらなグラフの古典的な表現はadjacency listです。隣接リストの利点は、ポインター/オブジェクトの同一性に依存するのではなく、名前で逆参照することです。そのため、構造内で任意の循環パスまたは自己参照パスを変更する必要なく表現できます。

ノードにアルファベット順に左から右/上から下に名前を付けます:

{:a [:c]
 :b [:d]
 :c [:a :d :e]
 :d [:b :c :e]
 :e [:c :d :g]
 :f [:h]
 :g [:e :h :i]
 :h [:f :g :i]
 :i [:g :h]}

ネットワーク内の要素は名前で検索され、その要素から出ている矢印は関連付けられた値としてベクトルで表されます。トラバーサルは、各反復でステップするノードをルックアップする再帰関数として実装できます。「ルート」は、（:iグラフ内で）トラバーサルを開始するために使用される単なる要素です。

ハッシュマップリテラルは通常の clojure 永続データ構造であるため、conj、update-in、などを使用して、さまざまな種類の挿入/分割再配置を実行できます。assoc

于 2015-02-23T19:07:04.887 に答える