Network X 2.0に入門する

目的

  • グラフ理論を利用したアルゴリズムを書く必要が出てきたので何ができるのか軽くおさらいしておく。

参考サイト

  1. 【Python】NetworkX 2.0の基礎的な使い方まとめ
  2. グラフ理論とNetworkX
  3. グラフの構造と種類

導入

まず前提としてAnaconda環境を用いる。

conda install -c anaconda networkx

Jupyer notebookで可視化するための環境も整えておく。私の環境はLinux Mint (≒Ubuntu)なのでaptで導入できた。

apt install graphviz libgraphviz-dev conda install -c anaconda pygraphviz

ここからはJupyter notebookで実行。まず肝心のnetworkxを読み込む。IPythonの可視化ライブラリも読み込んでおく。

import networkx as nx from IPython.display import SVG, display
Code language: Python (python)

グラフオブジェクトの作成

まずグラフオブジェクトを作成し, 頂点(Vertex)や辺(Edge)を追加していく。

以下は単純グラフ(Simple graph, 各頂点につながる辺が1本)を作成する場合。

g1 = nx.Graph() # Undirected graph g2 = nx.DiGraph() #Directed graph
Code language: Python (python)

以下は多重グラフ(Multigraph, 各頂点に繋がる辺が2本以上存在するかもしれない)を作成する場合。

g3 = nx.MultiGraph() # Undirected multigraph g4 = nx.MultiDiGraph() #Directed multigraph
Code language: PHP (php)

辺, 頂点を追加する

グラフオブジェクトを図示化するには以下のコードを実行する。

svg = SVG(nx.nx_agraph.to_agraph(Graph_object_name).draw(prog='fdp', format='svg')) display(svg)
Code language: JavaScript (javascript)

頂点を追加するには.add_nodeメソッドを使う。

G = nx.Graph() G.add_node("Hello") G.add_node("World")
Code language: JavaScript (javascript)

辺を追加するには.add_edgeメソッドを使う。有向グラフの場合, 第一引数から第二引数へ向かう辺が挿入される。

G.add_edge("Hello", "World")
Code language: JavaScript (javascript)

リストから一括で追加する場合は.add_nodes_fromまたは.add_edges_fromメソッドを使う。以下の例ではMultigraphを使ってHelloが自己ループ(loop)を形成するようにしている。

G = nx.MultiDiGraph() G.add_nodes_from(["Hello", "World", "Wonderful"]) G.add_edges_from([("Hello","Wonderful"),("Wonderful","World"),("Hello","Hello")])
Code language: JavaScript (javascript)

指定の頂点を通るパスを作成するにはadd_pathを用いる。(頂点と辺が自動生成される)

G = nx.MultiDiGraph() nx.add_path(G, ["Hello", "Wonderful", "World"])
Code language: JavaScript (javascript)

指定の頂点を通る閉路を作成するにはadd_cycleメソッドを用いる。(頂点と辺は自動生成される)

G = nx.MultiDiGraph() nx.add_cycle(G, ["Hello", "Wonderful", "World"])
Code language: JavaScript (javascript)

グラフオブジェクトから適宜必要な情報を抽出する

こちらが参考になる。「頂点の一覧/辺の一覧/特定の頂点を始点or終点とする終点or始点および辺の一覧/指定頂点と隣接する頂点のリスト」などの情報を取得できるようだ。

応用例

de Bruijn Graph を使った de novo アセンブリの発想がすごい件に記載のde Brujin Graphを作成しEuler pathを適用してみる。de Bruijn Graph を使ったde novo アセンブリではハミルトンパス問題をオイラーパス問題へと変換している。

オイラー路 / オイラー閉路のおさらい

オイラー路(Eulerian trail)は全ての辺を通る路のこと。直感的に言うと一筆書きできる路のこと。

オイラー閉路(Eulerian circuit)は全ての辺を一回だけ通る閉路のこと。直感的に言うと一筆書きして始点と終点をくっつける必要がある。

オイラー路の存在を効率よく計算するアルゴリズムは既に開発されている。

ハミルトン閉路のおさらい

ハミルトン閉路(Hamiltonian path)とは各頂点を含む閉路のこと。

ハミルトングラフとはハミルトン閉路を含むグラフのこと。

ハミルトンパス問題はNP困難。オイラーパス問題より難しい。

コード

# input original_seq = "GCCTACGAAGACAATTACTAGG" "GCCTACAAGACGA" read1 = "GCCTAC" read2 = "ACGAAG" read3 = "AGACAA" # k-merのリストを返すための関数 def return_kmer_list(k, read): kmer_list = [] for i in range(0,len(read) - 1): kmer_list.append(read[i:i + k]) return kmer_list kmer_list1 = return_kmer_list(2,read1) kmer_list2 = return_kmer_list(2,read2) kmer_list3 = return_kmer_list(2,read3) # ここは適当に追加しただけでなぜかDe Brujin graphになっているがadd_pathの挙動的に常にそうなるかは不明。たまたまかも。 G = nx.MultiDiGraph() nx.add_path(G, kmer_list1) nx.add_path(G, kmer_list2) nx.add_path(G, kmer_list3) # Euler pathを計算する euler_path = list(nx.algorithms.euler.eulerian_path(G)) # -> [('GC', 'CC'), ('CC', 'CT'), ('CT', 'TA'), ('TA', 'AC'), ('AC', 'CA'), ('CA', 'AA'), ('AA', 'AG'), ('AG', 'GA'), ('GA', 'AC'), ('AC', 'CG'), ('CG', 'GA'), ('GA', 'AA')] # Euler pathの計算結果を結合して元に戻す predicted_seq = "" for ele in euler_path: predicted_seq = predicted_seq + ele[0][0] predicted_seq = predicted_seq + euler_path[-1][1][0] print(predicted_seq) svg = SVG(nx.nx_agraph.to_agraph(G).draw(prog='fdp', format='svg')) display(svg)
Code language: PHP (php)

結果は「GCCTACAAGACGA」となり元の「GCCTACGAAGACAATTACTAGG」と完全一致する結果は得られなかった。k-merが小さすぎるため正しくない経路を排除するに十分な情報が得られなかったからだと考える。

本当はもっと大きいk-merでやるべきだと思ったがそうすると閉路ループを取り除くアルゴリズムなどを書く必要があり(閉路ループがあるとオイラー路が求められない)めんどくさくなったので今日はここまで。もしde Brujin Graphが今後必要になるようならきちんと勉強しようと思う。

コメント

Copied title and URL