ヒトなどの二倍体生物は、それぞれの親から1つずつ、2組の染色体を含んでいる。ハプロタイプと呼ばれる、各染色体の2つの異なるコピーを再構築することは、個体のゲノムを特徴付けるために重要である。このプロセスは、フェージングまたはハプロタイピングとして知られており、提供された情報は、遺伝性変異と遺伝子機能との間の関係、または遺伝性変異と疾患感受性との間の関係の分析などの多くの用途にとって根本的に重要であり得る。二倍体種において、ハプロタイピングは、各染色体の2つの親コピーに変異を割り当てることを必要とし、それは一塩基多型（SNP）の点で相違を示す。収集したサンプルからハプロタイプを大規模に直接実験的に再構築することはまだ費用効率が良くないので（Kuleshov et al、2014）、染色体コピーからシーケンシングされたリードのセットを考慮する計算アプローチ（ハプロタイプアセンブリ） が提案されている。可能であれば、予備のマッピング段階でリファレンスゲノムを用いて、リード（フラグメントとも呼ばれる）を未知のハプロタイプに割り当てる必要がある。これは、何らかの方法でシーケンシングおよびマッピングエラーを扱うことを含み、そして一般に最適化問題としてモデル化される計算タスクをもたらす（Lancia et al、2001； Lippert et al、2002）。
Minimum error correction (MEC) （Lippert et al、2002）は、ハプロタイプ構築のための著名な組み合わせアプローチの一つである。それは、SNPの値に対する最小数の補正で入力データを補正することを目的とし、その結果得られるリードは、それぞれハプロタイプを識別する２つのセットに明確に分割することができる。 wMEC (Greenberg et al、2004) は、問題の重み付き変形であり、各可能な補正は、対応する位置でそのSNP値に割り当てられた信頼度を表す重みと関連付けられる。この信頼度は、そのベースコールについてのシーケンシング中にエラーが発生した確率（フレッドベースのエラー確率）と、そのゲノム位置へのリードマッピングの信頼度との組み合わせである。そのような重みの使用は、精度を向上させる強力な方法として実験的に検証されている（Zhao et al、2005）。
次世代シーケンシング（ＮＧＳ）技術の出現は、二倍体生物のゲノムを組み立てる費用効果の高い方法を提供した。しかしながら、正確なハプロタイプをアセンブリするためには、いくつかの異なるヘテロ接合位置にまたがるのに十分な長さのリードを有することが必要である（Duitama et al、2012）。この種のデータは、PacBio RS II（http://www.pacificbiosciences.com/products/）やOxford Nanoporeフローセルのような一分子リアルタイムシーケンシング技術のような「未来世代」のシーケンシング技術の出現でますます利用可能になりつつある。
これらの技術は、10000塩基を超えるシングルエンドリードを生成するそれらの能力のおかげで、ペアエンドデータの必要性を排除し、そしてゲノムFinishingおよびハプロタイプアセンブリのようなタスクに既に使用されている（Smith et al、2012）。リード長に加えて、次世代のシーケンシング技術は、シーケンシングエラーが一様分布する新規な特徴を持つフラグメントを生成する。
最近、MECおよびwMECアプローチがロングリードの文脈で使用されており、長いフラグメントが伝統的なショートリードよりも正確にハプロタイプをアセンブリすることを可能にすることを確認している（Aguiar and Istrail、2012; Duitama et al、2012; Patterson et al、2014、 2015）。 MECはNP困難なので（Cilibrasi et al、2007）、厳密な解は指数関数的に複雑になる。問題の計算困難性に取り組む様々なアプローチが文献で提案されている。Integer linear programming テクニックが最近使用されている（Chen et al、2013）が、このアプローチではいくつかの「難しいブロック」を最適に解くことができなかった。（一部略）
WHATSHAP（Patterson et al、2014）と呼ばれる2番目のアプローチは、ロングリードを処理できるwMECの最初の正確なアルゴリズムである。 20xまでのカバレッジ範囲でシミュレートされたロングリードのデータに対して良好な精度を得ることができ、そして全ての以前の正確なアプローチよりも優れていることが示された。ただし、20倍を超えるカバレッジを処理することはできず、その限界に近づくとそのパフォーマンスは明らかに低下する。（複数段落省略）
カバレッジ15〜20倍のシミュレーションデータセットの結果は、HAPCOLはWHATSHAPと同じくらい正確だが（平均誤差約2％を達成）、より高速で大幅にメモリ効率が高いことを示している（約2倍高速、約28倍メモリ使用量が少ない）。 HAPCOLの効率により、精度をさらに向上させることができる。実際、実験結果は、HAPCOLが標準ワークステーション/小型サーバー上で25倍のカバレッジでデータセットを処理できることを示している（一方、WHATSHAPはすべての利用可能なメモリ、256 GBを使い果たした）。カバレッジ25倍でHAPCOLによって再構成されたものは、カバレッジ20倍で再構成されたものよりも約9％正確である。
HP
インストール
依存
- CMake (>= 2.8)
- GNU make
本体 Github
#1GBほどあるのでダウンロード時は注意
git clone https://github.com/AlgoLab/HapCol.git
cd HapCol/
mkdir -p build
cd build
cmake ../src
make
> ./hapcol -h
# ./hapcol -h
* INFO (main :c/HapCol.cpp:167 ) 10:09:30 | HapCol (master@97d4a5e-clean)
* INFO (main :c/HapCol.cpp:171 ) 10:09:30 | Starting...
Program options:
-h [ --help ] produce (this) help message
-i [ --input ] arg file containing the input reads (in WIF
format)
-o [ --haplotypes ] arg file where the computed haplotypes will
be written to
-u [ --discard-weights ] discard weights
-x [ --no-ambiguous ] do not mark ambiguous positions with Xs
-A [ --all-heterozygous ] all-heterozygous assumption
-U [ --unique ] input as unique block
-e [ --error-rate ] arg (=0.05) read error rate
-a [ --alpha ] arg (=0.01) significance (smaller is better)
* INFO (main :c/HapCol.cpp:178 ) 10:09:30 | Arguments:
* INFO (main :c/HapCol.cpp:179 ) 10:09:30 | Initialized? False
* INFO (main :c/HapCol.cpp:180 ) 10:09:30 | Input filename: ''
* INFO (main :c/HapCol.cpp:181 ) 10:09:30 | Haplotype filename: ''
* INFO (main :c/HapCol.cpp:182 ) 10:09:30 | Discard weights? False
* INFO (main :c/HapCol.cpp:183 ) 10:09:30 | Do not add X's? False
* INFO (main :c/HapCol.cpp:184 ) 10:09:30 | All-heterozygous assumption? False
* INFO (main :c/HapCol.cpp:185 ) 10:09:30 | Input as unique block? False
* INFO (main :c/HapCol.cpp:186 ) 10:09:30 | Error rate: 0.05
* INFO (main :c/HapCol.cpp:187 ) 10:09:30 | Alpha: 0.01
* FATAL(main :c/HapCol.cpp:190 ) 10:09:30 | Arguments not correctly initialized! Exiting..
テストラン
> head ../docs/sample.wif
# head ../docs/sample.wif
36950998 C 0 10 : 36951355 G 1 7 : 36951968 G 0 3 : 36952090 C 0 11 : 36952098 C 1 28 : 36954126 A 0 15 : 36961286 G 0 20 : 36961747 C 0 23 : 36961983 T 1 24 : 36966400 G 0 21 : 36966495 T 0 26 : 36984266 T 0 31 : 36993308 G 0 10 : # 60 : NA
36950998 C 0 12 : 36951355 G 1 7 : 36951968 G 0 22 : 36952090 C 0 33 : 36952098 C 1 23 : 36954126 A 0 4 : 36961286 G 0 26 : 36961747 C 0 34 : 36961983 T 1 33 : 36966400 G 0 29 : 36966495 T 0 24 : # 60 : NA
36950998 C 0 12 : 36951355 G 1 9 : 36951968 G 0 26 : 36952090 C 0 36 : 36952098 C 1 38 : 36954126 A 0 27 : 36961286 G 0 29 : 36961747 C 0 24 : 36961983 T 1 37 : 36966400 G 0 32 : 36966495 T 0 8 : 36984266 T 0 38 : 36993308 G 0 35 : # 60 : NA
36950998 C 0 13 : 36951355 G 1 37 : 36951968 G 0 19 : 36952090 C 0 31 : 36952098 C 1 29 : 36954126 A 0 17 : 36961286 G 0 33 : 36961747 C 0 24 : 36961983 T 1 35 : 36966400 G 0 34 : 36966495 T 0 11 : # 60 : NA
36950998 C 0 14 : 36951355 G 1 8 : 36951968 G 0 20 : 36952090 C 0 17 : 36952098 C 1 23 : 36954126 A 0 14 : 36961286 G 0 26 : 36961747 C 0 35 : 36961983 T 1 23 : 36966400 G 0 19 : 36966495 T 0 21 : 36984266 T 0 19 : # 60 : NA
36950998 C 0 16 : 36951355 G 1 32 : 36951968 G 0 24 : 36952090 C 0 6 : 36952098 C 1 11 : 36954126 A 0 32 : 36961286 G 0 6 : 36961747 C 0 20 : 36961983 T 1 31 : 36966400 G 0 11 : 36966495 T 0 10 : # 60 : NA
36950998 C 0 17 : 36951355 G 1 31 : 36951968 G 0 24 : 36952090 C 0 11 : 36952098 C 1 36 : 36954126 A 0 24 : 36961286 G 0 24 : 36961747 C 0 22 : 36961983 T 1 27 : 36966400 G 0 26 : 36966495 T 0 26 : # 60 : NA
36950998 C 0 17 : 36951355 G 1 37 : 36951968 G 0 19 : 36952090 C 0 36 : 36952098 C 1 23 : 36954126 A 0 15 : 36961286 G 0 3 : 36961747 C 0 38 : 36961983 T 1 8 : 36966400 G 0 4 : 36966495 T 0 15 : 36984266 T 0 36 : 36993308 G 0 9 : # 60 : NA
36950998 C 0 20 : 36951355 G 1 34 : 36951968 G 0 24 : 36952090 C 0 32 : 36952098 C 1 26 : 36954126 A 0 36 : 36961286 G 0 9 : 36961747 C 0 33 : 36961983 T 1 2 : 36966400 G 0 35 : 36966495 T 0 28 : 36984266 T 0 15 : 36993308 G 0 33 : # 60 : NA
36950998
どのリードがどのSNPアレルをどれだけカバーしているかをwifフォーマット (introduced in (Patterson et al., RECOMB, 2014)) で記載している。このwifフォーマットについてはGithubの"Input format"の項目で説明されている。
.wifファイルを指定して実行
./hapcol -i ../docs/sample.wif -o haplotypes.txt
- --input (or -i), which specifies the file containing the reads in input (in WIF format);
- --output (or -o), which specifies the file for the computed haplotypes.
出力
>head haplotypes.txt
# head haplotypes.txt
101101110111110110111100101111011100011001110110100010010X10100100111001110010011100100111110011010001100010000010100010010011001100110011110011110101101001011011011010111101001001110111101001010101111101111101000110100110101000010101011100111100111001100001111000100110000101110010010111010111011000110110010101000001010011000111010101000001010010110101111100000101001101100111000100001001110100100111111000000111011001100111000000010001011100001010100100010001110010010011100110101111100011010011000100011000111101101010001010101001011111110010000
010010001000001001000011010000100011100110001001011101101001011011000110001101100011011000001100101110011101111101011101101100110011001100001100001010010110100100000101000010110110001000010110101010000010000010111001011001010111101010100011000011000110011110000111011001111010001101101000101000100111001001101010111110101100111000101010111110101101001010000011111010110010011000111011110110001011011000000111111000100110011000111111101110100011110101011011101110001101101100011001010000011100101100111011100111000010010101110101010110100000001101111
引用
HAPCOL: accurate and memory-efficient haplotype assembly from long reads
Yuri Pirola, Simone Zaccaria, Riccardo Dondi, Gunnar W. Klau, Nadia Pisanti, Paola Bonizzoni
Bioinformatics, Volume 32, Issue 11, 1 June 2016, Pages 1610–1617,
関連
