本文是来自Stanford Compression Workshop 2019的演讲,作者是来自SambaNova Systems公司的Victoria Povich。在过去的数十年间,DNA测序发生了巨大的进步。例如对人类基因组的测序的价格,已从十年前的10万美元降低至如今的1千美元。技术的进步和价格的降低,使得我们能够有能力去对人类周边的世界进行基因测序。于此同时,测序的简便也带来了一些其他方面的挑战。例如如何对海量数据进行分析以及如何保护基因组中的隐私信息。
人类的基因组由30亿个碱基对组成,若将其看做ACTG的字母组合,以2进制表示每一个字母的话,每个人的基因数据量也有100GB左右。我们可以利用传统算法对基因序列进行储存,传输和分析,但是这样做的成本却很高。若利用基因组学的知识,找出基因中的特定片段,或者找出基因的特征,就可以实现对基因数据的压缩。
获取到基因组数据后的首要问题就是如何读出基因的位置,其中最核心的问题就是读取映射问题。不管是物种间还是同一物种内,基因的相似程度是很高的。理想情况之下,如果我们有一个完整的参考基因组,那在存储其他基因组时,我们只需要存储它们之间的差别即可,这样就可以消除DNA数据中的大量冗余。但实际中我们并非这样处理,主要原因是我们很难辨别出这些基因的差别。但是如果我们采用更大的数据块进行分析时,我们可以更为高效的进行分析数据。我们采用构造基于长DNA片段的Hash表或者参考表,然后在若干候选点中进行基因比对,这样就大大减少了基因匹配的时间。
接着作者介绍了三个例子: