講義ノート

http://mlab.cb.k.u-tokyo.ac.jp/courseware  


2017年度 生物情報ソフトウエア論 I & II
2017/4/6 – 7/27 毎週木曜日2限(10:25-12:10 105分)
理学部3号館 412講義室 (講義資料のパスワードは講義時間に連絡します)

生物情報ソフトウエア論 I
DNA 等の巨大文字列処理を例に O(n log n)-時間 および 線形時間アルゴリズムの作り方を学ぶ。
プログラミング初めての人が手軽に実行できるページ集
例 codechef   のページ  実行例

  • (4/6)  講義の背景  講義資料1
    Quick Sort / Introspective Quick Sort   講義資料2
  • (4/13)  Ternary Split Quick Sort / Radix Sort / k 番目の元を線形時間で計算
  • (4/20)  大規模配列の超高速処理 / suffix array とは?  講義資料3
  • (4/27)  Doubling 法で O(n log n) 時間で suffix array を構築する
    induced sorting 法で線形時間で suffix array を構築する 講義資料4
  • 4月末〆切 Sorting の演習課題1    (5/4) みどりの日で休みです
  • (5/11)   induced sorting 法で線形時間で suffix array を構築する
    Burrows-Wheeler Transform で線形時間検索 講義資料5
  • (5/18)  DNA 中の類似配列の検索 / Seeded alignment 講義資料6
  • (5/25)  比較ゲノム / Chaining 講義資料7
  • (6/1) 生物情報ソフトウエア論 I 筆記試験 (時間 10:25 – 12:10 )
  • 6月末〆切 Suffix array (演習課題2−3) / Burrows-Wheeler Transform (演習課題4)

2016年度 生物情報科学演習(森下研究室担当分)
日程 2016/12/6 – 2016/1/12  毎週火―金曜日3-4限
場所 理学部3号館 302演習室

選択課題 2つ以上を選択
課題① 森下真一    編集距離問題の計算量下界の現状/クラスタリングのNP困難問題
課題② 鈴木裕太   線形時間アルゴリズム DNA 区間推定問題
課題③ 甕 湧一      Persistent Homology
課題④ 鈴木慶彦   アラインメントの超高速化とゲノムアセンブリ


2016年度 生物情報ソフトウエア論 I & II
2016/4/14 – 7/28 毎週木曜日2限(10:25-12:10 105分)
理学部3号館 412講義室 (講義資料のパスワードは講義時間に連絡します)

生物情報ソフトウエア論 I
DNA 等の巨大文字列処理を例に、O(n log n)-時間および線形時間アルゴリズムの作り方を学ぶ。

(4/7)    休講
(4/14)
講義の背景 Sortの講義資料(若干説明を追加 4/20)
Quick Sort  例(Cのコード)
(4/21)
ヒープとスタック / Quick Sort の改善 / Introspective Quick Sort
プログラム / Ternary Split Quick Sort / Radix Sort / k 番目の元を線形時間で計算する
Introspective Sort を実装している様々なライブラリ
k 番目の元を線形時間で計算するアルゴリズムの計算量解析
(4/28) 
大規模配列の超高速処理 / suffix array とは?
Doubling 法で O(n log n) 時間で suffix array を構築する Larsson-Sadakane アルゴリズム
4月末〆切
Sorting の演習課題1
(5/12) 
induced sorting 法で線形時間で suffix array を構築する
(5/19)
DNA 中の完全一致配列の検索 / Burrows-Wheeler Transform で問合せを線形時間検索
(5/26)
DNA 中の類似配列の検索 / Seeded alignment
(6/2)
生物情報ソフトウエア論 I 筆記試験 (時間 10:25 – 12:10 )
試験問題 解答例

生物情報ソフトウエア論 II
(6/9) 休講
(6/16)
Chaining, 比較ゲノム
(6/23)
遺伝子転写, DNAメチル化, ヒストン修飾
(6/30)
クロマチン構造、DNA3次元折り畳み構造
6月末〆切
Suffix array (演習課題2−3) / Burrows-Wheeler Transform (演習課題4)
(7/7)
人類遺伝学の基礎: allele, genotype, haplotype, 連鎖不平衡
(7/14)
人類遺伝学の基礎: 全ゲノム相関解析 (Genome-wide Association Study, GWAS)
(7/21)
2限 人類遺伝学の基礎: 連鎖解析 (Linkage Analysis), Lander-Green algorithm
個人ゲノム解読
3限 6/9 分の補講  機械学習における過学習の回避, AdaBoost algorithm
(7/28)
生物情報ソフトウエア論 II 筆記試験 (時間 10:25 – 12:10 )
試験問題 解答例
8月末〆切
Chaining 課題(演習課題5)


2015年度 生物情報科学演習 (森下研究室担当分)

2015/12/8 – 2016/1/14  毎週火―金曜日3-4限
理学部3号館 302演習室
Teaching Assistant: 市川和樹, 鈴木裕太, 鈴木慶彦, 富岡真悟
TA控室 理学部3号館 309号室

  • 12/9
    イントロダクション(森下)
    課題①−1(鈴木裕太) (資料 20151208w_ensyu.pdf 課題データ)
  • 12/11 課題①−2(市川和樹)(資料:ichikawa_20151211.pdf)
  • 12/15 関連研究 ヒトゲノム解読の現状 原稿 (森下)
  • 12/16 関連研究 1分子実時間シーケンシング 原稿 (森下)
  • 12/17 〆切 課題①−1
  • 12/17 説明 課題②(市川和樹)(資料:K-means-ACC_20151217.pdf)
  • 12/22 説明 課題③(鈴木裕太)(資料: 20151222w_ensyu , MDL基準によるモデル選択)
  • 12/24 説明 課題④(鈴木慶彦)(資料: スライド(1/12再アップロード)、C言語でのスレッドの使い方)
  • 12/30  〆切 課題①−2
  • 1/5  再説明 課題② (市川和樹)
  • 1/6 再説明 課題③ + アレル特異的DNAメチル化の動向(鈴木裕太)
  • 1/12 再説明 課題④ +
    メタゲノムアセンブリとメチル化研究の動向(鈴木慶彦)(ゲノムアセンブリについて)
  • 1/14 関連研究
    ロングリード(PacBio+bionano)を使ったゲノムアセンブリの最先端(市川和樹)(資料:ichikawa_20160114.pdf)
    クロマチン構造研究の数理的アプローチ(森下)(資料
  • 1月末 → 2/15 〆切 課題②、③、④
  •  〆切ですが 2/15 は大変で少し延ばして欲しいという要望もありましたので、3/10 まで受け付けます。よろしくお願いします。。(2/16 森下)

2015年度 生物情報ソフトウエア論 I & II
2015/4/9-7/30 毎週木曜日2限(10:25-12:10 105分)
理学部3号館 412講義室 (講義資料のパスワードは講義時間に連絡します)

生物情報ソフトウエア論 I: DNA 等の巨大文字列処理を例に、O(n log n)-時間および線形時間アルゴリズムの作り方を学ぶ。

(4/9)  講義の背景 
1分子シーケンサーのビデオ PacBio  Nanopore

(4/9-16) Quick Sort / ヒープとスタック / Introspective/ Ternary Split / Radix
プログラム 例(Cのコード)
Introspective Sort を実装している様々なライブラリ
Sorting のアニメーション  

(4/23)  大規模配列処理 / Suffix array, Doubling O(n log n)
息抜き シーラカンスゲノム 論文 図2(Conserved limb enhancers) 岡田典弘先生の解説

(4/30) Linear-time suffix array construction by induced sorting
アルゴリズム実装のための補足資料 (Nong らの実装方式を解説)

4月末〆切 Sorting の演習課題1   (5/7) 講義振替日で休みです

(5/14)  k番目の要素を選択する線形時間アルゴリズム
             DNA 中の完全一致配列の検索 / Burrows-Wheeler Transform

(5/21, 28)  DNA 中の類似配列の検索 / Seeded alignment
息抜き 4300万人の家系図

(6/4) 生物情報ソフトウエア論 I 筆記試験 (時間 10:25 – 12:10 )
実施済み 試験問題 解答案  解答案_問題2
(著作権がないのでパスワードもないです)
(問題4(4)は mt=4 の場合を解説しており解答例として不備があります。出題している mt=3 の場合は同じような論法で修正する必要があります。)

6月末〆切 Suffix array (演習課題2−3)/ Burrows-Wheeler Transform (演習課題4)

生物情報ソフトウエア論 II: DNAの応用について学ぶ。具体的には、異なる種のゲノム間の比較、ヒトゲノムと疾患関連遺伝子の探索、ヒトゲノムから分かる民族の分類、DNA・ヒストンの化学的修飾と機能ドメインの推定、DNA3次元構造。

(6/11)  DNA 間の比較ゲノム / Chaining and comparative genomics / 平衡2分木の活用

(6/18)  人類遺伝学の基礎 allele, genotype, haplotype, 疾患関連遺伝子探索
アレルと遺伝子型の現在最大級DB ExAC (Broad@MIT/Harvard)  例 ALDH2
ハプロタイプの推定 契機となった論文(2012) Moleculo (2014)  10X(2015)

(6/25)  人類遺伝学の基礎 連鎖不平衡, GWAS(全ゲノム相関解析)

(7/2)  人類遺伝学の基礎 連鎖解析,   パーソナルゲノム解析

1分子シーケンサーのビデオ PacBio  Nanopore

(7/9,16)  遺伝子転写, DNAメチル化, ヒストン修飾, DNA3次元折り畳み構造

(7/16) DNA3次元折り畳み構造予測(概略)
Organization of the Mitotic Chromosome (YouTube)
A 3D Map of the Human Genome (YouTube)

(7/23)   変異体イメージからの量的形質を測定する画像処理技術
楕円をあてはめる最適化アルゴリズムの解説 (9MBもある MS Word -> PDF)
上田泰己先生の組織透明化の論文に掲載された美しい動画へのリンク

(7/30) 生物情報ソフトウエア論 II 筆記試験 (時間 10:25 – 12:10 )

8月末〆切 Chaining 課題(演習課題5)


2015年度 卒研ローテーション (4-5月) 

Epigenome 関係の論文

ENCODE 2012/2015 の ChromHMM の実装 (2012)  ページ7-8がポイント。この論文の責任著者の Manolis Kellis 先生 (MIT Broad Institute) が5月に来日します。5/22 に下記の会議で講演していただきます。同じセッションで PacBio の創業者でSMRT sequencing を研究開発した Jonas Korlach 博士も講演していただけます。

第11回国際ゲノム会議(11AGW)

Discriminative prediction of mammalian enhancers from DNA sequence (2011)  DNA 上の一部の配列モチーフから epigenome state を予測できるという論文。String kernel, SVM を利用。広く使われている。Methodsの support vector machine のパラグラフが大事。

Predicting the human epigenome from DNA motifs  (2015) 同じくDNA 上の一部の配列モチーフから epigenome state を予測できるという論文。position-weight matrix (PWM) を利用。

Hi-C DNAの3次元的折り畳み構造

哺乳類での3次元構造:Topological domains in mammalian genomes identified by analysis of chromatin interactions (Nature, 2012)  クロマチン構造が凝縮する topological domain を同定ている。ヒストン修飾との関係も分析している。

1分子計測:Single-cell Hi-C reveals cell-to-cell variability in chromosome structure (Nature, 2013)  初めて1分子で Hi-C を実現した論文

高解像度 Hi-C:A 3D Map of the Human Genome at Kilobase Resolution Reveals Principles of Chromatin Looping (Cell, 2014) Hi-C を2009年に提唱した Lieberman Aiden らが解像度を 1 Kb レベルに向上させた論文

おまけ:Inching toward the 3D genome (Science, 2015) 楽しい1頁の記事です。上の論文の解説なのですが、米国が3次元クロマチン構造およびヌクレオソーム構造解明に本気になったという4D Nucleosome program にも触れています。

Edelsbrunner, H., A short course in computational geometry and topology (2014)  代数幾何と代数トポロジーの教科書。学内からは pdf を無料で入手できますが、上手くゆかない場合は、教えてください。

1塩基変異情報からの人種の分類

イギリス人の分類 (2015) 非常に細かい分類ができる

この分類で使われた高感度な計算方法 ChromoPainter and fineSTRUCTURE (2012) haplotype 情報を活用

ADMIXTURE 上の論文が出る前には最も利用されていた方法 (2009)

1分子リアルタイムDNAシーケンサーの動画

PacBio  Nanopore Nanopore の精度を評価した論文(2015)

Transgenerational Epigenetic Inheritance

DNA methylation

The Salk Insitute – Ecker Lab – Publications

H3K9me3

A nuclear Argonaute promotes multigenerational epigenetic inheritance and germline immortality

Amplification of siRNA in Caenorhabditis elegans generates a transgenerational sequence-targeted histone H3 lysine 9 methylation footprint

Structural Variation 構造変異

Resolving the complexity of the human genome using single-molecule sequencing. Nature. 2014. Sanger法で読めなかったヒトゲノムのギャップ領域をPacBio で埋め、Structural variation を網羅的に解析した論文。Evan Eichler のグループからの論文。

Genome sequencing identifies major causes of severe intellectual disability (2014) 構造変異が知能障害と関連している可能性を示唆した論文

参考になるページ

Changing the Definition of Sequencing, 10X  動画が美しい。この原理については例えば

Whole-genome haplotyping using long reads and statistical methods

を読んで下さい。

BGI 世界最大級のゲノムシーケンシングセンター

Transgenerational Epigenetic Inheritance について補足情報 (4/23更新 / 鈴木より)


2014年度 生物情報科学演習 (森下研究室担当分)

2014/12/16 – 2015/2/3  毎週火―金曜日3-4限

理学部3号館 302演習室

Teaching Assistant: 市川 和樹, 鈴木 裕太, 甕 湧一

演習課題の提出は 2015/3/20 までにお願いします。

課題① 大規模な生物データを取得して、情報処理するのに役立つツール

課題② 生物データとクラスタリングの高速化(NP困難問題と枝刈り法)

課題③ エピゲノムとDNA 区間推定問題(線形時間アルゴリズム)

課題④ Multi-Dimensional Scaling を使った DNA3次元構造予測(動的計画法、線形代数)

2014/12/16 13:00-

はじめに 森下真一 (資料: agenda2014.pdf)

課題④の解説 甕 湧一 (資料 2015/1/27 更新済み: chromatin_conformation_2014、 入力データ: 必要な方は甕までメールをください)

2014/12/17 13:00-

課題①の解説 市川和樹 (資料:ichikawa_20141217.pdf)

鈴木裕太 (資料 PDF 課題データ)

2014/12/18 13:00-

課題②の解説 市川和樹(資料:K-means-ACC_2014.pdf)

2014/12/19 13:00-

課題③の解説 鈴木裕太(資料 PDF)

Unix の利用方法

Windows に Ubuntu を入れる方法

PuTTYと公開鍵暗号をつかって学科のサーバーにログインする際に参考になるページ(学科サーバーのIDは玉田先生からもらって下さい。)

PuTTY で鍵交換方式による SSH 接続

PuTTY の使い方

情報生命科学専攻の大学院生用の並列サーバへのアクセス方法

※サーバーのアドレスを変更すれば学科サーバに繋げることができます。

2014/12/23 – 2015/1/4 冬休み

2015/1/6 13:00-

課題①に関係して

高いGC率のDNAが読みにくい理由(2012 年の資料)

Sanger法で読めなかったヒトゲノムのギャップ領域をPacBio で埋めた論文 (Resolving the complexity of the human genome using single-molecule sequencing. Nature. 2014.)

2015/1/8 13:00-

課題①に関係して

病気の原因となるDNA変異についての従来の考え方(環境要因、遺伝体質)よりも幹細胞分裂回数に注目すべきことを示唆した論文 解説

Tomasetti, C., & Vogelstein, B. (2015). Variation in cancer risk among tissues can be explained by the number of stem cell divisions. Science, 347(6217), 78–81

2015/1/13 13:00- 課題④の解説 甕 湧一 (資料: chromatin_conformation_2014、 入力データ: 必要な方は甕までメールをください)

2015/1/15 13:00- 課題①の解説 市川和樹 (資料:ichikawa_20141217.pdf)

課題②の解説 市川和樹(資料:K-means-ACC_2014.pdf)

2015/1/20 13:00- 課題③の解説 鈴木裕太(資料 PDF)

2015/1/23 13:00- 課題③に関連する話題 DNAメチル化と string kernel  森下

2015/1/27 13:00- 課題④に関連する話題 3D構造モデルのtopological data analysis 甕 湧一

2015/1/29 13:00- 月曜日の授業振替日でした… すいません

2015/2/3 13:00-

情報基礎実験の冬学期授業評価アンケートを取るので集まって下さい。

日本学術振興会 Nobel Prize Dialogue Tokyo (この会議の参加登録は直ぐに一杯になってしまいましたがネット配信するそうです。23日に紹介すべきでした…)

演習課題の提出は 2015/3/20 までにお願いします。


2014年度 生物情報ソフトウエア論 I & II

2013/4/10-7/24 毎週木曜日2限 理学部3号館 412講義室 講義資料 (パスワードは講義時間に連絡します)


2013年度 生物情報科学演習 (森下研究室担当分)

2013/12/10 – 2014/1/29  毎週火―金曜日3-4限 理学部3号館 302演習室

Teaching Assistant: 市川 和樹, 大石 晶一朗, 鈴木 裕太

はじめに

課題① 大規模な生物データを取得して、情報処理してみる。

その時に役立つツールを紹介。

2013/12/10 13:00- shell script, make, R (大石) (資料 : 20131210soishi)

2013/12/11 13:00- sed, awk, gnuplot (鈴木) (資料:1211w_ensyu.pdf) (課題 : enshu.tar.gz)

〆切 2013年12月末

課題② suffix array, BWT, Chaining アルゴリズムを使った大規模ゲノム配列の比較と構造多型の推定 担当 大石

2013/12/17 13:00- 課題の解説 (資料:20131217soishi.pdf)

課題③ 生物データのクラスタリングと高速化 NP 困難問題の枝刈りアルゴリズムの実装  担当 市川

2013/12/18 13:00- 課題の解説(資料:K-means-ACC_2013.pdf)

課題④ DNA を機能区間に分類する 線形時間区間推定アルゴリズムの実装 担当 鈴木

2013/12/19 13:00- 課題の解説(資料: w1219.pdf)

2014/1/9 13:00- ヒトゲノムの謎 (課題②と関係する研究最前線の状況) 森下

2014/1/14-17 2014/1/14 13:00- DNA修飾周辺の話題 (課題④と研究最前線の状況) 森下

2014/1/16 (木) 13:00- 課題の再説明 課題② (Chaining 担当 大石), 課題④ (機能区間分類 担当 鈴木)

2014/1/21-24, 28,29 2014/1/21 (火) 13:00- 課題の再説明 課題③ (クラスタリング 枝刈り 担当 市川)

2014/1/28 (火) 13:00- 2014/1/28 (火) 13:00-

最終回 予測、観測、発見の例 森下


2012年度 生物情報科学演習 (森下研究室担当分) 2012/11/6 – 12/7 理学部3号館 302演習室 12月中は毎週水曜日 大石晶一朗君が 309号室で質問等に答えてくれます。 演習資料 (パスワードは演習時間に連絡します)

補足資料(ミスマッチおよびギャップを許して問合せ配列をゲノム上にアラインメントする)
プログラミング言語参考書