8月第2週の勤務

DBCLS

今週行った事

1.illlumina，http://www.454.com/publications-and-resources/all-publications.aspの文献リストから実験IDを抽出し，GEOのIDをSRAのIDに変換．
2.SRAのIDを抽出できたPubMedの論文から，meshが現れる頻度を求める．


1. GEO -> SRAの変換
実験IDの抽出は以前行ったが，取り漏らしがありそうだったので再抽出する．
文献リストからPubMedIDを抜き取る．論文リストのhtmlファイルから，文字列'ncbi'がある行に並んでいる数字をファイルに出力する．



$ grep 'ncbi' (論文リストが載っているhtmlファイル) | grep -o -E '[0-9]+' | sort | uniq > （抽出したPubMedのIDを出力するファイル）
結果のファイルに明らかに異なる数字(日付など)があったので，これらは手作業で除く．
PubMedのIDから，論文中の実験IDとSRAへ変換したIDを出力するプログラムを作成する．
出力結果は，PubMedID・PMCID・PubMedから抽出したIDのDB名・PubMedから抽出したID・PMC本文から抽出したID・SRAに変換したID．


18326688    2493403  GEO       GSE10115        -            -

18329356    -        -         -               -            -

18329373    -        GEO       GSE10437        -            SRA000234

19146710    2687794  -         -               GSE12640     SRA008248


2. PubMedからmeshの頻度を求める
目的は，SRAのIDがありそうな論文の傾向を調べる事．
PubMedのxmlファイルからmeshを抽出するプログラムは先週作成したので，複数のPubMedIDからmeshの個数をカウントして出力するプログラムを作成．結果は，現れたmeshとその回数．



Transcription Initiation Site	3

Polymorphism, Single Nucleotide	9

Genes, Bacterial	1

次回

meshの頻度を降順で出力する．
頻度が高いmeshをクエリで投げて取得した論文から，実験IDを抽出する．

8月第1週の勤務

DBCLS

目標：PubMedの論文と，書かれている次世代シーケンサーの実験ID(SRA)の対応を取りたい．

今週やったこと

1. 論文が出た時にはSRAのデータベースがなく，GEOのIDが書かれているものがあるかも．論文から抽出したGEOのIDを，SRAに変換してみる．


2. 論文検索で投げるクエリを考えてみる．これまで抽出した結果から，次世代シーケンサーのIDが書かれているものに共通の特徴はないか？

結果

1. "illumina"でクエリを投げてID抽出した結果を使って変換してみる．GEOのIDか書かれていた論文("GSE"を含むIDが書かれているもの)で，GEO -> SRA変換できたものは139本中16本．ただし，1本の論文に複数のGEOのIDが書かれているものがほとんどで，GSE -> SRA変換した個数は143個．(139本の論文からは187個のGEOのIDを抽出．)
結果のファイルはillumina_gse_sra.tab，"GEOのID"，"PMCのID"，"PubMedのID"，"GSE->SRA変換したID"の順番．


2. PubMedには，meshという論文のキーワード的なものが付けられている．次世代シーケンサーのIDが書かれているものに多く出てくるmeshのワードを調べる．
今週作成したのは，1つの論文に付与されているmeshを出力するところまで．
入力：pubmedのxmlファイル．結果：付与されているmesh．こんな感じ↓



$ java -cp ./bin GetMesh pubmed11244113.xml 

Quantitative Trait, Heritable

Cereals

Physical Chromosome Mapping

Poaceae

DNA Fingerprinting

Genome, Plant

次回

  • 1.のGEO -> SRAの変換を手作業で行ったので，ID抽出の時に同時に行う様に変更．これまで解析してきた他のものも解析し直したい．
  • PubMedのIDを複数入力して，付与されているmeshの個数を出力するプログラムを書く．

GEOのデータからGEOのIDとPubMedのIDを抽出

DBCLS

今までの「PubMedの論文データ → 実験データID」の逆で、「実験データ(データベース：GEO) → PubMedの論文データID」を抽出しました。IDはメタデータの以下の文字列に着目しました。
・GEOのID
　　!Series_geo_accession = xxxx
　　xxxxがGEOのID
・PubMedのID
　　!Series_pubmed_id = xxxx
　　xxxxがPubMedのID


GEO → PubMed の対応は結構取れそうでした。

PubMedから外部データベースのIDを抽出

DBCLS

今回の変更点

(1) PubMedのXMLに書かれているPubMed Central (PMC)のIDには、今後追加される予定のIDも書かれています。これらを区別できるようにしました。
(2) 論文から抽出するIDを、外部データベースのID全てを抽出する様に変更しました。


(1) 今後PMCに追加されるものは、"/PubmedArticleSet/PubmedArticle/MedlineCitation/OtherID"のPMCのIDの後ろに[Available on (日付)]と書かれています(例：[Available on 09/16/10])。これに該当する箇所がxmlファイルにあれば、PMCのIDの出力箇所に"Available_on_(日付)"と出力します。

(2)外部データベースのIDは "/PubmedArticleSet/PubmedArticle/MedlineCitation/Article/DataBankList/DataBank" に書かれています。
・タグ "DataBankName"：外部データベースの名前
・タグ "AccessionNumberList/AccessionNumber"：外部データベースのID
PMCのxmlファイルでは外部データベースのIDがタグ付けされていないため、PubMedのxmlファイルのみ解析しています。


結果の出力：PubMed_IDからxmlファイルを取得・解析し、
"PubMed_ID PMC_ID 外部データベース名 外部データベースのID"
を出力します。

PubMedのXMLからID抽出

DBCLS

PubMedIDから論文中に含まれている外部DBのID抽出の続き。

htmlファイルから抽出したIDの修正

前回http://www.illuminakk.co.jp/support/literature_GA1.shtmlから抽出したIDに取り漏らしがあったので修正しました。前回の

  • htmlファイル中の "http://www.ncbi.nlm.nih.gov/pubmed/"

以外に、

  • "http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=PubMed&dopt=Citation&list_uids=18436779"

と書かれているIDも抽出できるように変更しました。

ID抽出するプログラムの仕様変更

ファイルに書かれているIDを抽出できる用に変更しました。

  • オプション-fを付ければファイルから読み込み
  • それ以外の時にはPubMedID1個を抽出

文献中のIDと実験IDの対応確認

PubMedの文献中から抽出した実験IDと、実験IDから対応を取ったPubMedIDの対応を確認しました。現時点では、相互対応があまり取れていなさそうな感じがします。

牧場活動記録

論文中に含まれているIDの抽出をしました。

作業手順

(1)EFetch経由で、PubMedIDからxmlファイルの取得
(2)取得したxmlファイルからPubmed CentralのIDの抽出（前回までのタグに着目、XPathを使用）
(3)EFetch経由で、Pubmed CentralのIDから、論文全文が書かれたxmlファイルを取得（クエリを投げるときに、db=pmc&retmode=xml&id=(取得したID) にする）
(4)取得したxmlファイルからIDの抽出（それぞれのDBのID構造に着目、正規表現でPattern、Matcherを使用）


(1)から(3)は前回までに作成したプログラムをほぼそのまま使用し、実際に作成したのは(4)のみ。その後、(1)から(4)をまとめて実行するプログラムを作成しました。（PubMedIDを投げたら(4)まで一気に実行。）


作成したプログラムを使って、http://www.illuminakk.co.jp/support/literature_GA1.shtmlにある論文リストから、PubMedIDを抽出しました。
・htmlファイルを取得
・htmlファイル中の "http://www.ncbi.nlm.nih.gov/pubmed/" に着目。後ろの8文字を取得
それを上記のプログラムに投げるシェルを書いて自動化しました。


IDの抽出で使用したJavaのクラスPatternやMatcherは、正規表現を使用できるので文字列抽出の時には便利そうです。

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

ゼミ

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

今回は、前回の最小全域木の実装、クラスタリング、Huffman符号です。(〜4章)

PrimとKruskanのアルゴリズムの実装（最小全域木問題）

頂点数がn個、辺の本数がm本のグラフを入力とした場合、どちらのアルゴリズムも、O(mlog(n))で実装可能です。ただし、そのためにはUnion-Findデータ構造というものを使用します。

Union-Findデータ構造

一つのノード集合を木構造で表します。ノード v が属している木の根が u の場合、ノード v が属する集合は u とする構造です。
ノード v が属しているグループを求めるためには O(log n) かかります。
利点は集合の併合が簡単にできることです。例えば、根がノード u の集合と根が w の集合を併合する場合には、u を w の子ノードとすれば併合できます。

クラスタリング

単連結法の紹介と最小全域木との関連をやりました。
最小全域木から最も辺の重さが大きい辺(k-1)本削除すると、k個のクラスタ（ノード集合）に分類できます。これは、単連結法のクラスタリングと等価です。

Huffman符号

文字列を0と1のビット列で符号化します。その際、全文章を表す01の文字列の長さが最小となるようにします。また、曖昧性が無いように、どの文字を表すビット列も他のビット列の接頭語にならないようにします。
そのためには二分木をT作成し、葉に文字をラベル付けします。葉に行き着くまでに左の辺を通ったら0、右を通ったら1で符号化します。
全文章を表す文字列の長さが最小となるためには、出現頻度が高い文字に対して短いビット列を与えます。この方法で木Tを作成すると、木の深さが浅い（根から近い）葉に出現頻度の高い文字が、深いところには出現頻度の低い文字がくるように接頭語の木Tを求めればいいことになります。そのために、最も出現頻度が低い文字から葉を割り当てていく、ボトムアップで木を作成します。