本篇介紹兩種 Graph-genome 的技術
Introduction
原本的 reference 是 linear genome(e.g GRCh38)。而 graph-genome 就是做成 graph 的樣子(見下圖)
最大的優點就是 可以把所有已知的 variants 全部塞進 reference 裡，當然，什麼都不加的話，就是在 linear reference 上操作，所以保底就是不會輸一般的方式。
我們在此就介紹 2019 的這兩篇有關 graph-genome 的 paper:
- Hisat2(Kim et al., 2019)
- Graph Genome Pipeline(Rakocevic et al., 2019) (我在這簡稱GGP好了)
那 graph genome 跟直接 mapping 到 multiple sequences 相比會有什麼好處呢 (比如說 map 到 HLA 的 27990 多條可能的 sequences 上)。第一是 graph 可以明確地說出哪裡是共用的，所以比較不用擔心 multiple mapping 的情形
第二就是減少 reference-bias(GGP 的 paper 提到這個名詞)，我個人認為拉，就是等價於 mismatches 的 quota 用在哪裡的問題
+------------+--------------------------------+---------------+
| | Linear | Graph |
+------------+--------------------------------+---------------+
| Quota of | Error + Novel + Known Variants | Error + Novel |
| mismatches | | |
+------------+--------------------------------+---------------+產生 reference-bias 的原因很簡單，就是跟 reference(e.g. GRCh38) 不一樣時就需要特別花 mismatch 去處理。但
如果能把我們早就已知的 alleles 加在 reference 上，那麼 mismatch 就可以專心處理 Sequencing Error 跟 Novel alleles 的問題。
Methods
如前面介紹的，我選這兩篇 paper 就是因為他們剛好各代表兩個流派(?)
GGP 是用 hash 來做的，就是暴力的把 graph 的所有可能 k-mer 都 hash 過一遍。而 Hisat2 則是 BWT，對每個點出去的做 sorting，尾巴就是 BWT string，很神奇吧
Result
不外乎就是跟 BWA-mem BWA-GATK Bowtie2 這種大家都很熟的 tools 比較。
所以從上圖可以知道，graph-based 保底就是 linear reference only，然後把各種 database 加上去後，甚至可以多 bwa 2%。這裡 GGP 做了一個測試，把 identity graph 拿進來比較，也毫無意外的是 100% ，畢竟是從 target genome build 出來的，graph 跟 原來的 genome 一摸一樣，更嚴格的說這個就是 unbiased-mapping 。
Why better
然後說明為什麼沒有 reference-bias 比較好的實際證據，我統整成四點說明
- Large deletion(Structure Variation) 會有問題。
從下圖可以看到，平常 bwa-mem 可以處理短的 deletion 但是長一點就不行了，所以你會看到 IGV 裡面呈現 reads 邊邊沒對齊的樣子，而在 graph 中，就只是一個 edge 連過去而已，很 native，所以能輕鬆處理兩個 haplotype 都有 deletion 的情形。
2. 而且一般使用 Linear reference 在有 Structure Variation 的情況下 recall rate 不高的問題，可能是那些對不齊的影響。
3.linear reference 會在 highly mutated region 出現 coverage (depth) 不夠的問題(下圖)，原因也是 reference-bias ， mismatch 越多，就越不容易 align 上去，自然 variant calling 也會出問題。
4. 基於觀察3 ，GGP 把自己的 False Positive 的 allele 拿去做 Sanger ，做了一部分，然後發現至少有 60% 原本的 False Positive 居然是正確的。追根究柢就是目前的標準方式(bwa-GATK) 是 linear genome 本質就不容易做出來。
5. 觀察3，graph-genome 更擅長 hyper-mutation 的區域(如下圖)，比如說 DNA-fingerprint(CODIS)，HLA(IMGT)。Calling 的作法是把有 map 在那段區域的 reads 拿出來後，用 de bruijn graph 來 assemble ，據說可以
- Phasing (找出 一人兩條的 haplotype)
- 找出 novel 的 indel 或者是 alleles
- de-noise
- 解 ambiguous
Graph-Genome augmentation
Add all rare alleles
當然，直覺想就是那把全世界的 variants 都加進去好了，沒錯，
但除了速度會被拖慢外，兩篇 paper 都有說到 accuracy 會受影響(但剛好只有提到一兩句話)
… likely map to multiple and often incorrect location(Hisat2)
… slight drop in variant calling accuracy(GGP)
Add parents’ alleles
比如要分析家族的 alleles 時，我們可以在 graph 上增加父母的 alleles，使得分析更準，也就是違反孟德爾遺傳的情況越少。
Add population’s alleles
使用 Qatar genome project cohort 的資料，裡頭共有 4 個族群。
上圖左 GGP 先用 graph 把 1/5 人 novel alleles called 出來，然後加進去 graph 後，再對 4/5 人做一次 variant calling
其實根本沒有加任何外部資料，但找到 novel SNPs 還變高(變兩倍 見下圖)，可見 reference-bias 是蠻巨大的。
所以我就想說如果能 iterative 的循環做下去(上上圖右，原本 paper 只有做一輪)，是否可以連 sample-bias 寫消除掉，也就是連 novel 都被加入 graph 裡了，變成 真·unbiased-mapping，我們只要專心處理 sequencing error 就好了。(話說 medium 沒有表格，真的很糟糕…)
+------------+------------------+---------------+----------------+
| | Linear | Graph | Graph + called |
+------------+------------------+---------------+----------------+
| Quota of | Error + Novel | Error + Novel | Error |
| mismatches | + Known Variants | | |
+------------+------------------+---------------+----------------+其他(細節)
簡易的 Read Mapping Pipeline 如下
- GGP: hash -> clustering seeds by MAQ -> bitap + SIMD-optimized Smith– Waterman -> de bruijn graph -> haplotyping and novel alleles
- Hisat2: BWT + repeat -> de bruijn graph -> variant calling and novel alleles (Hisat2 似乎不用 extension 嗎)
有關 seed, extension, clustering seeds, bitap, Smith– Waterman 可以參考前一份文章
MAQ 這個 score 是拿來計算 seed alignment 的好壞，其實這個作法是參考 bwa-mem 的(意思是不輸 bwa-mem)
這兩篇有一致的地方，就是會把 align 好的其中一小段拿出來使用 de bruijn graph 來組出原本的 haplotype。不過這邊的細節我就沒有讀很熟。
Speed
Hisat2 其實有引用 GGP 但沒有拿來比較，但是我們可以從相對速度略知一二
- GGP 快 bwa-mem 10%
- HISAT2 快 bwa-mem 2–3倍
- HISAT2 比 vg(Variation graph, 也是 graph-genome 的作法，可惜真的很慢, Garrisonet al. 2018) 快很多很多倍
至於為什麼 Hisat2 會很快，除了用 bitap 加速以外，其中一項原因是 Hisat2 多蓋了 repeat genome 這個 database。可以想像說如果你 map 到 repeat database 的其中一條，就代表的現實中你 map 到了 10 個可能的位置，除了快，還可以節省很多貯存空間。這個 database 建造也很簡單，你把 simulated reads(也可以 real data) 拿去 map 到 gnome 上，如果超過 5 次，就記錄下來，然後把所有的 reads 用 de Bruijn graph 去 merge 出 repeat sequences，然後就完成了
Conclusion
我覺得 graph-genome 是一個天生就能解決把已知 alleles 考慮進 reference 的好方法，再加上可以在 graph 上做 bwa 代表著根本很 compatible，遲早會取代 linear-genome 的。而且說不定也能解決 transcriptome mapping(就是只 mapping exons)，因為就只是多一條 edge 代表 intron 的 deletion 而已
Hisat2 還是開源的，也就是說，我們想要做更適合 based on graph 的 variant calling 方法是比較容易的
請多按 clap 鼓勵我寫文章 QQ，雖然這篇文章是希望推坑這個好東西。
Reference
- Kim, D., Paggi, J. M., Park, C., Bennett, C., & Salzberg, S. L. (2019). Graph-based genome alignment and genotyping with HISAT2 and HISAT-genotype. Nature biotechnology, 37(8), 907–915.
- Rakocevic, G., Semenyuk, V., Lee, W. P., Spencer, J., Browning, J., Johnson, I. J., … & Ji, S. G. (2019). Fast and accurate genomic analyses using genome graphs. Nature genetics, 51(2), 354–362.
- Garrison, E., Sirén, J., Novak, A. M., Hickey, G., Eizenga, J. M., Dawson, E. T., … & Paten, B. (2018). Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nature biotechnology, 36(9), 875–879.
- Li, H. (2013). Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arXiv preprint arXiv:1303.3997.
