PubMedのXMLから情報抽出(2)

DBCLS

先週のPubMedのXMLから情報抽出を、JavaのXml構造を扱うDOM(Document Object Model)を使って書き直しました。
"/PubmedArticleSet/PubmedArticle/MedlineCitation/PMID/text()" という形式で直接指定できるXPathの存在に気づいたのが実装後だったため、NodeListとかElementを使って一段階ずつ子ノードを見ていく…という方式で実装しています。 （XPathの参考：Java XPath API）
あとは、論文中に登場するIDの方式（最初の3文字がxxxという文字で、その後数字がくる、など）を教わりました。

輪講：アルゴリズムデザイン（第2回）

ゼミ

月曜の輪講のメモです。第1回はこちら↓
輪講：アルゴリズムデザイン（第1回）

今回は、前回証明できなかったところの証明(アルゴリズム4.1、4.2、4.3)と、最小全域木の証明までです。（〜p136）

アルゴリズム4.1 区間スケジューリング

問題

それぞれ開始時間s(i)と終了時間f(i)がある、n個の要求集合{1,2,...,n}に対し、できるだけ多くの要求を処理できるようにスケジューリングをします。

アルゴリズム

f(i)が最小の要求から順に処理します。処理した要求の集合をAとします。

証明

証明することは、以下の二つです。
（4.1）Aに含まれる要求は、どの二つも同時に処理されることはない（共存可能）である。
（4.3）Aは最適解である。
まず、(4.1)共存可能について。この証明は本では省略されています。アルゴリズムでは要求iを選択してAに加えたあと、iと同時期に処理しなければならない要求を、解となる集合Aの候補から除いています。そのため共存関係になることはありません。
次に、(4.3)について。最適解である要求集合をOとします。本当はA=Oを示したいのですが、最適解Oはパターンが複数考えられるため、Oで処理する要求数とAの要求数が等しいこと（|O|=|A|）を示します。そのために、最適解Oが受理した要求を処理した順番にO={j_1,j_2,...,j_m}、同様にAも処理した順にA={i_1,i_2,...,i_k}とします。これに対し、r ≦ kに対してf(i_r) ≦ f(j_r)が成り立ちます（命題（4.2））。命題（4.2）はrに関する帰納法で証明しました。
（4.3）は、背理法を用いて証明します。「Aより多くの要求を含む最適な集合Oが存在する、つまりk < m となるOが存在する」を仮定し、これを命題（4.2）を用いて棄却しました。

アルゴリズム4.2 区間分割アルゴリズム

問題

それぞれ開始時間s(i)と終了時間f(i)があるn個の要求集合{1,2,...,n}に対し、同時に処理している要求数dができる限り少なくなるようにスケジューリングをします。（どの要求がどの資源で処理されているのかを、ラベル{1,2,...,d}を付与します。）

アルゴリズム

開始時刻時刻s(i)が早い順番に探索します。要求iについては、時刻s(i)の時点で処理されているどの要求も持っていないラベルを付けます。

証明

要求集合の深さがdの場合、資源数がd個の最適なスケジュールが上記のアルゴリズムで求めることができます。
そのために、深さd個の要求があるときには、少なくともd個の資源が必要であること（命題(4.4)）と、アルゴリズムで得られるスケジュールで必要な資源の個数がd個であることを示します。
命題(4.4)は、要求がd個重なっているところは必ずd個の資源が必要です。
アルゴリズムの解の方は、かち合っている要求の個数をt(0≦t≦d-1)とすると、要求に対して付けられるラベルの個数は(d-t)個。(d-t)≦0となることはないため、アルゴリズムの解はd個の資源で要求を処理することができます。

アルゴリズム4.3 遅延最小化スケジューリング

問題

要求iに対し、期限d_iがある要求集合全てのスケジューリングを考えます。求めたいスケジュールは、期限内に終わらなかった要求（要求の終了時刻f(i) > d_iの要求）の遅延時間、(f(i)-d_i)が最も長いものが、最小となるスケジュールです。

アルゴリズム

要求の期限d_iを早い順にソートし、その順番で要求に応えていきます。

証明

Aが最適解であることを示します。アルゴリズムで求められるAは、アイドル時間（要求が何も処理されていない時間）がなく、反転もない解が求まります。そのため、アイドル時間がなく反転もない最適解Oがあることを命題(4.7)から(4.9)で証明し、(4.10)で最適解Oの遅延時間L'とアルゴリズムの解Aの遅延時間Lが等しいことを示しました。


前回の証明についてはここまでです。ここからは、最小全域木のアルゴリズムについてです。

最小全点木問題（最小全域木問題）

問題

グラフGを入力。Gの全頂点集合Vを含み、かつ連結であり、辺の重さの総和が最小となる部分グラフを求めます。求められる結果は木であり、最小全域木と呼ばれます。

アルゴリズム

アルゴリズムは、次の3つが紹介されています。
・Kruskalのアルゴリズム：グラフの辺の重さが最も小さい辺から全域木Tの辺として選択します。その際、閉路ができない辺だけを解に追加します。
・Primのアルゴリズム
グラフの適当なノードsからはじめ、sが持つ辺の中で重さが最小の辺(s,v)を木に追加します。そして、次にvについても同様のことを繰り返します。
・逆順序アルゴリズム（Reverse-Delete Algorithm）
グラフ全体から、重みが大きい辺を削除していく。その際、孤立頂点ができないように削除していきます。

証明

（4.17）カット特性：二つの集合Sと(V-S)を考えます。辺e=(v,w)で、v∈S、w∈(V-S)である辺の内、重さが最小の辺は、どの最小全域木にも含まれる。
（4.20）閉路特性：CをグラフGの任意の閉路とし、Cの中で重さが最大の辺は、どの最小全域木にも含まれない。
（4.17）と（4.20）は背理法を用いて証明しました。
また、KrustalとPrimのアルゴリズムはカット特性を、逆順序アルゴリズムは閉路特性を用いて証明しています。

PubMedのXMLから情報抽出

DBCLS

PubMedのXMLファイルから、以下を抽出して出力するプログラムを作成しました。括弧の中は抽出に使用したタグです。

  • PubMedID ()
  • タイトル ()
  • 雑誌名の略称 (タグの)
  • 出版された日付 (タグの中の、、、)
  • 外部データベースへのリンク ()
  • PubMedCentralのID、PubMed Centralで全文持っている論文のみある ()

PubMedIDに関しては、でも抽出はできますが、タブにある（今回抽出したい物とは別のID）も抽出されてしまうため、を使用しました。
外部データベースへのリンクは複数あるときもあれば、一つもないときもあります。また、PubMedCentralのIDは無いときもあります（IDがある場合には1つ）。
今回は単純にファイルの文字列検索で作成しました。
JavaでXmlの木構造を使う方法がありそうなので、次回はこの辺りのお勉強する予定。うまくいけばPubMedID抽出もに着目してできるようになる…？

輪講：アルゴリズムデザイン（第1回）

ゼミ

研究室の輪講で、「アルゴリズムデザイン」を読みます。

アルゴリズムデザイン

アルゴリズムデザイン

第1回目は第4章グリーディアルゴリズムからスタートで、p103〜130を読みました。（第1〜3章は各自で読みましょう。）
以下、今回登場した問題の設定とアルゴリズムをメモしています。

アルゴリズム4.1 区間スケジューリング問題

n個の要求（それぞれ開始時刻s(i)と終了時刻f(i)がある）に対して、どれだけ多くの要求に答えられるようにスケジューリングができるのかを求める問題です。最適化するのは時間ではなく、答えられる要求数です。
1.開始時間が早い物から要求に応える
2.要求に応える時間が最短のものから選ぶ
3.他とかぶる区間が最も少ない物から選んでいく
上記の3つの手法が最初に提案されていますが、どの手法も最適解を求めることはできません。
最適解が求められるアルゴリズムは、終了時刻f(i)が最も早い要求から答えていく手法です。（最適解になる証明、計算時間は次回？）

アルゴリズム4.2 区間分割アルゴリズム

4.1と同じく、n個の要求（開始時間s(i)と終了時刻f(i)）に対するスケジューリングの問題です。ただし、今回は同時に複数個の要求に応えることができ、各要求に対してどこで要求に応えていいるのか、{1...d}のラベル付けをすることでスケジューリングをします。同時に答える要求の最大個数dをいかに少なくして、スケジューリングをするのかを解きます。
アルゴリズムは、開始時間s(i)が最も早いものからスケジューリングを決めていきます。その要求iよりも前に開始している要求がまだどれも持っていないラベルを、要求iのラベルとします。（複数個ラベルの候補がある場合には、任意に1つ選びます。）

アルゴリズム4.3 最大遅延最小化スケジューリングアルゴリズム

4.1、4.2とは違い、各要求に開始時刻と終了時刻はありません。その代わり、各要求に期限が与えられており、全ての要求のスケジューリングを考えます。同時に答えられる要求は1つのみです。求める解は、要求の遅延の長さの最大が最も小さい解です。例えば、要求aとbに対してスケジューリングした結果、要求aが3分遅延、bが2分遅延であれば、このスケジューリングの遅延はaの3分となります。この遅延が最も短い解を求めます。
アルゴリズムは、期限が最も早い要求から順に答えていく方法です。この手法で、最適解が求められます。（証明は次回？）

アルゴリズム4.4 最適キャッシングアルゴリズム

データにアクセスする順番があらかじめ分かっている時に、キャッシュにどの様にデータを保存すれば効率が良いのかを求める問題です。「効率が良い」とは、キャッシュにあるデータを追い出す回数が少ないことです。
アルゴリズムは、キャッシュから追い出すデータを決める時に、次に参照される時が最も遅いデータを追い出します。

アルゴリズム4.5 ダイクストラのアルゴリズム

辺に重みのあるグラフで、ノードsからtまでの最短経路を求める問題です。辺の重さに負の値は無いとします。
アルゴリズムについては丁寧に解説してくれているWebページがあると思うので、ここでは省略します。

アルゴリズム4.6 最小全点木アルゴリズム（最小全域木アルゴリズム）

辺に重みのある無向グラフから、グラフの全部のノードを通り、辺の重さが最小となる部分グラフを求める問題です。この問題の解は、木（閉路を持たないグラフ）になります。
今回は問題の紹介までで、実際のアルゴリズムは次回です。

読んでおきたい論文

論文

今まで勉強したことをまとめるにあたって、読み直したい論文、新たに読んでみたい論文が出てきたので、まとめました。全てグラフを解析している論文です。読んだ後に気が向いたら、内容をまとめてアップするかもしれません。

モジュラリティの最大化

GN法

Finding and evaluating community structure in networks
M.E.J.Newman and M.Girvan
Physical Review E 69, 026113 (2004)
Community structure in social and biological netwirks
M.Girvan and M.E.J.Newman
PNAS Vol.99 p7821-7826 (2002)
トップダウン型でグラフクラスタリングを行います。クラスタリング結果の指標としてモジュラリティを定義しています。

Newman法

Fast algorithm for detecting community structure in network
M.E.J.Newman
Phys.Rev.E 69, 066133 (2004)
GN法で提案されているモジュラリティを最大化することを目的としたクラスタリング手法です。

CNM法

Finding community structure in very large networks
Aaron Clauset, M.E.J.Newman and Cristopher Moore
Physical Review E 70, 066111 (2004)
Newman法をより速く計算できる手法です。

それ以外

Mining Cohesive Patterns from Graphs with Feature Vectors

Flavia Moser, Recep Colak, Arash Rafiey, Martin Ester , SDM09
頂点に特徴ベクトルがあるグラフから、共通の特徴を持ち、かつ辺が密な頂点集合を抽出します。ソーシャルネットワークとバイオのネットワークを解析しています。

Community Learning by Graph Approximation

Bo Long, Xiaoyun Wu, Zhongfei Zhang, Philip S. Yu , ICDM07
グラフのリンク構造に着目して頂点を分類します。コミュニティ内の頂点は、密に辺を張るコミュニティが同一になるように分類をします。

Modeling cellular machinery through biological network comparison

Roded Sharan, Trey Ideker
Nature Biotechnology 24, p427-p433
異なる生物種間でネットワークの比較をしています。

PubMedのアブストラクトの取得

DBCLS

NCBIのeUtils経由で、PubMedにクエリを投げてxmlを取得しました。

eUtils

PubMedやGenBankなどのデータベースから、検索結果が膨大になるxmlを取得する場合、NCBIに何度もアクセスすることになります。そのような場合に利用するサイトがeUtilsです。

作業

PubMedのアブストラクトのxmlを取得するために行ったのは、以下の二つの行程です。
1.EsearchにPubMedのクエリを投げ、取得したxmlから検索に必要なID、クエリを取得。
2.取得したIDなどの情報をクエリとし、EFetchから論文のアブストラクトが書かれたxmlファイルを取得。
Javaのプログラムで作成し、パッケージは java.net.* と java.io.* を使用しました。

EFetch

順番が前後しますが、まずは作業工程2から。
検索クエリからアクセスするアドレスを作成し、そこに書かれていることをファイルに書き込んでいきます。
http://eutils.ncbi.nlm.nih.gov/corehtml/query/static/efetchlit_help.htmlのExampleにクエリとその結果のアドレスの例が書かれています。
今回はEsearchで検索クエリのIDを取得し、そのIDをEFetchに投げます。そのために指定する必要があるのは、retmax、retstart、query_key、WebEnvです。retstartは検索結果の上から何件目から結果を取得するか、retmaxは一度に取得する件数を、query_keyとWebEnvはESearchで取得した検索IDの指定ができます。

ESearch

次に作業工程1です。
http://eutils.ncbi.nlm.nih.gov/corehtml/query/static/esearch_help.htmlのExamplesにアクセスするアドレスの例が書いてあります。EFetchに投げるクエリに必要なQueryKeyやWebEnvを抽出するために、xml形式で取得し、やで囲まれている文字列を取得しました。そのために、usehistory=y、retmode=xmlもESearchのクエリにします。また、からは検索結果の件数を得ることができます。検索結果を全て取得したい場合や、結果を複数回に分けて取得したい場合に使用します。
あとは取得した文字列を使って上記のEFetchにアクセスするアドレスを作成して、xmlファイルに書き込みます。

MeCab単語の追加

DBCLS R MeCab

先日のRMeCabのインストールに引き続き、MeCabの辞書へ単語の追加をしました。http://mecab.sourceforge.net/dic.htmlを参考にしています。
システム辞書とユーザ辞書、二つの追加方法がありますが、今回はユーザ辞書への追加をします。
disease.csvというファイルを準備し、このファイルに書かれている単語を辞書に追加します。disease.csvの文字コードはutf-8です。
まず、disease.csvがあるフォルダに移動し、辞書のコンパイルをします。私の場合、辞書も文字コードはutf-8であるため、コンパイルは以下のように実行します。

$  /usr/local/libexec/mecab/mecab-dict-index -d/usr/local/lib/mecab/dic/ipadic -u disease.dic -f utf-8 -t utf-8 disease.csv

各オプションは

-d DIR: システム辞書があるディレクトリ
-u FILE: FILE というユーザファイルを作成
-f charset: CSVの文字コード
-t charset: バイナリ辞書の文字コード

とのことです。文字コードの指定、ファイル名などは必要に応じて変更しましょう。
disease.dicが作成されたことを確認します。

$ ls
disease.csv	disease.dic

/usr/local/etc/mecabrcに作成した辞書を追加します。一般ユーザではmecabrcを変更する権限が無いため、sudoコマンドで実行します。編集にはemacsを使用しました。

$ sudo emacs /usr/local/etc/mecabrc

mecabrcに以下の一行を追加します。

userdic = ***/disease.dic

***はdisease.dicがあるフォルダの絶対パスを記入します。
MeCabの動作の確認をします。辞書に新たに追加した単語を入力して、結果が正しく返ってくるか確認しましょう。