3

私は、いくつかのバイオインフォマティクスを行うための特殊なクワッド ツリーを開発しています。qtree のタイプは次のとおりです。

type base = A | C | G | T | ROOT  ;;
type quad_tree = Nd of bases * quad_tree  * quad_tree  * quad_tree * quad_tree 
             | Empty
             | Leaf of int ref ;;

let init_quad_tree = Nd(ROOT, Empty,Empty,Empty,Empty);;
let new_node b = Nd(b,Empty,Empty,Empty,Empty);;

構築時または歩行時にこれらの木を照合すると、次のようになります。

let rec add_node  base k qtree = 
  let rec aux k' accum qtree' = 
    if k' = k then
  match qtree' with
  | Nd(bse, Empty, cc, gg, tt) -> Nd(bse, (Leaf(ref accum)),cc,gg,tt)
  | Nd(bse, aa, Empty, gg, tt) -> Nd(bse, aa,(Leaf(ref accum)),gg,tt)
  | Nd(bse, aa, cc, Empty, tt) -> Nd(bse, aa,cc,(Leaf(ref accum)),tt)
  | Nd(bse, aa, cc, gg, Empty) -> Nd(bse, aa,cc,gg,(Leaf(ref accum)))
  | Leaf _ -> qtree'
  | Empty -> Leaf(ref accum)
  | _ -> qtree'
else
match qtree' with
| Leaf(iref)  -> iref := !iref + 1; qtree'                        
| Nd(bse, Empty,Empty,Empty,Empty) ->  (*all empty*)
    (
    match base with
    | A -> Nd(bse,(new_node base),Empty,Empty,Empty)
    | C -> Nd(bse,Empty,(new_node base),Empty,Empty)
    | G -> Nd(bse,Empty,Empty,(new_node base),Empty)
    | T -> Nd(bse,Empty,Empty,Empty,(new_node base))
    | _ -> qtree'
    )
...
| Nd(bse, Empty,(Nd(_,_,_,_,_) as c),(Nd(_,_,_,_,_) as g),(Nd(_,_,_,_,_) as t)) -> 
    (
    match base with
    | A -> Nd(bse,(new_node base),(aux (k'+1) (accum+1) c),(aux (k'+1) (accum+1) g),(aux (k'+1) (accum+1) t))
    | C -> Nd(bse,Empty,(aux (k'+1)(accum+1) c),(aux (k'+1)(accum+1) g),(aux (k'+1)(accum+1) t))
    | G -> Nd(bse,Empty,(aux (k'+1)(accum+1) c),(aux (k'+1)(accum+1) g),(aux (k'+1)(accum+1) t))
    | T -> Nd(bse,Empty,(aux (k'+1)(accum+1) c),(aux (k'+1)(accum+1) g),(aux (k'+1)(accum+1) t))
    | _ -> qtree'
    )
...
| Nd(bse, (Nd(_,_,_,_,_) as a),(Nd(_,_,_,_,_) as c),(Nd(_,_,_,_,_) as g),(Nd(_,_,_,_,_) as t)) ->
...

基本的に、そこにある 16 の組み合わせすべて (空または Nd のいずれかである 4 つのサブツリー) をカバーする必要があります。これは大量の入力であり、エラーが発生しやすくなります。

ただし、これはコード生成に役立つ非常に規則的な構造です。実際には Ruby スクリプトを使用してこのコードを生成するつもりでしたが、campl4 または新しい -ppx スタイルの「マクロ」(より適切な用語がないため) でこれが可能かどうか疑問に思っています。もしそうなら、どうすればこれらの方向のいずれかで始めることができますか?

4

1 に答える 1

1

機能慣用ツリーでは、サブツリー内の他のすべてのノードが空であっても、すべてのノードがそのサブツリーのルートです。明示的な ROOT 定義を折りたたんで、カウンター プロパティをリーフ ノードにマージします。

type base = A | C | G | T ;;
type quad_tree = 
  | Node of base * int ref * quad_tree * quad_tree * quad_tree * quad_tree
  | Empty

しかし、あなたがそれに取り組んでいる間は、その参照を明示的な int にして、永続的なデータ構造を使用できるようにすることもできます。

type quad_tree = 
  | Node of base * int * quad_tree ...
  | Empty

ウォーキング/構築は、あなたが何をしたいのか（パスに正確に一致する文字列を表す各ノード）の私の理解に基づいてそれほど複雑である必要はありません.毎回ツリーの新しいバージョンを作成してください. ちょっと醜いバージョン：

let shorter str = String.sub 1 ((String.len str) - 1);;

let rec add_str base str = match base with
  | Empty -> 
     let ch = String.get str 0 in
     if ch = 'A' then add_str Node('A', 0, Empty, Empty, Empty, Empty) (shorter str)
     else if ch = 'C' then add_str Node('C', 0, Empty, Empty, Empty, Empty) (shorter str)
     ...
  | Node(b, v, aa, cc, gg, tt) ->
     let len = String.length str in
     if len = 0 then Node(b, v + 1, aa, cc, gg, tt) else
     let ch = String.get str 0 in
     if ch = 'A' then match aa with
       | Empty -> Node(b, v, (add_str Empty str), cc, gg, tt)
       | Node(b', v', ... , tt') -> add_str Node(b', v', ... , tt') (shorter str)
     else if ch = 'C' then match cc with
       | Empty -> Node(b, v, aa, (add_str Empty str), gg, tt)
       | Node(b', v', ... , tt') -> add_str Node(b', v', ... , tt') (shorter str)
     ...
于 2015-04-18T11:07:14.890 に答える