ACM通信
评论文章
21世纪的计算生物学:压缩算法缩放
图片来源:Peter Crowther Associates
计算生物学家用计算代替实验室程序来回答生物和生物医学问题，希望以大大降低的成本获得更准确的答案。在过去的20年里，在生成生物数据方面取得了前所未有的技术进步;下一代测序、质谱、微阵列、低温电子显微镜和其他高通量方法导致了数据的爆炸。然而，这种爆炸式增长是喜忧参半的。一方面，数据的规模和范围应该能让我们对遗传和传染病、癌症、基础生物学甚至人类迁移模式有新的见解。另一方面，研究人员生成的数据集如此庞大，以至于很难对其进行分析，以发现为潜在生物过程提供线索的模式。
关键的见解
当然，电脑变得越来越快，越来越经济;每一美元计算机硬件的可用处理量几乎每一两年翻一番;对于存储容量(图1)．
2002年，当第一个人类基因组测序完成时，计算能力的增长仍与基因组数据的增长速度相匹配。然而，用于人类基因组计划的测序技术在2004年左右被取代，因为现在被称为下一代测序的出现。基因组测序的材料成本在过去十年中直线下降，整个人类基因组测序的成本不到1000美元。因此，可供研究人员使用的基因组数据数量正以每年10倍的速度增长。
数据的增长给研究人员带来了重大挑战。25目前，许多生物“组学”应用需要我们存储、访问和分析大型数据库。解决这些挑战的一个方法是采用云计算。谷歌，Inc.和Broad研究所合作将GATK(基因组分析工具包)引入谷歌云(https://cloud.google.com/genomics/gatk)．Amazon Web Services也通常用于计算生物学研究和企业(例如，DNAnexus)。31然而，虽然云计算使研究人员从维护自己的数据中心中解放出来，并在不需要持续使用计算资源时提供了节省成本的好处，但它并不是万灵药。首先，构成云数据中心的计算机系统本身受到半导体技术和摩尔定律改进的约束。因此，云计算并没有真正解决组学数据比摩尔定律指数增长更快所带来的问题。此外，面对疾病爆发，例如2014年西非的埃博拉病毒大流行，往往需要在偏远的实地站点进行分析。虽然现在可以将测序设备和有限的计算资源带到远程站点，但互联网连接仍然受到高度限制;访问云资源进行分析可能是不可能的。
计算机科学家经常利用各种数据的结构，以减少时间或空间的复杂性。在计算生物学中，这种方法暗中为研究人员提供了很好的服务。现在的经典方法，如主成分分析(PCA)降低了数据的维数，以简化分析和揭示显著特征。3.另一个例子是，聪明的索引技术，如Burrows-Wheeler Transform (BWT)利用了序列结构的各个方面3.加快计算速度，节省存储空间。本文重点介绍了利用生物数据独特的结构来处理生物数据增长的前沿算法进展;获得新的生物学见解的算法并不是它的重点。
生物资料的种类
在分子生物学的中心教义中，DNA被转录成RNA, RNA被核糖体翻译成多肽链，即氨基酸序列，这些氨基酸单独或复合被称为蛋白质。蛋白质折叠成复杂的低能量结构，起到细胞机器的作用;DNA序列决定了氨基酸序列，氨基酸序列又决定了蛋白质的折叠结构。这种结构最终决定了蛋白质在细胞内的功能。某些种类的RNA也起着细胞机器的作用。研究人员已经开发出从这一过程的各个层面收集生物数据的方法，从而产生了大量关于DNA、RNA和蛋白质的序列、丰度、结构、功能和相互作用的数据。这些数据中的大部分都符合标准的大数据分析方法;然而，在本文中，我们主要关注生物数据的例子，这些例子展示了用于创建可扩展算法的额外可利用结构。
序列数据，无论是核苷酸序列(使用4个字母字母表示4个DNA或RNA碱基)还是蛋白质序列(使用20个字母字母表示20个标准氨基酸)，都可以通过几种方式获得。对于蛋白质和RNA序列数据，质谱(可以确定蛋白质序列和相互作用)和RNA-seq(可以确定RNA序列和丰度)让科学家也可以推断它可能翻译到的基因的表达起着关键作用。然而，随着下一代测序(NGS)技术的出现，最大的序列数据是DNA。为了更好地理解NGS序列数据的结构，我们将扩展NGS方法。
在基因组时代的黎明，桑格测序是最广泛使用的解读基因组的方法。然而，最近的NGS方法，从Illumina的“合成测序”开始，由于大量的并行性、低成本和简单的样品制备，使吞吐量大大提高。Illumina测序和其他NGS方法，如SOLiD、Ion Torrent和454焦磷酸测序，不能像阅读装订书籍那样端到端读取单个DNA分子。相反,在鸟枪测序， DNA分子被切成许多小片段;我们从这些片段中生成读取从一端或两端(图2一个)．这些reads必须按照正确的顺序排列在一起，才能拼凑出整个基因组。目前的读取长度通常在50到200个碱基之间，尽管某些技术(例如PacBio)可以提供更长的读取。因为没有一种测序技术是完全正确的，测序机也提供了一种质量分(或对DNA碱基的信心测量)与每个位置相关。因此，NGS读取是一串DNA字母，加上一串编码基本调用质量的ASCII字符。排序运行将产生许多重叠的读取。
虽然测量丰度以生成基因表达数据(有关更多信息，请参阅ACM数字图书馆中本文附带的源材料)适合于聚类分析和概率方法，但数据中的高维数和噪声提出了重大挑战。主成分分析在降低基因表达数据的维数方面显示出了希望。这些数据及其面临的挑战一直是其他文章的重点，3.这一点在这里只会稍微提一下。
如前所述，功能服从形式，所以除了序列和表达外，结构在生物数据科学中也扮演着重要的角色。然而，我们并不只对RNA和蛋白质结构感兴趣;小型化合物是相关结构数据的额外来源，因为它们经常与较大的RNA和蛋白质兄弟相互作用。分子的物理结构可以通过x射线晶体学、核磁共振、电子显微镜和其他技术来确定。一旦确定，就有各种各样的方法来表示这些结构，从分子键的标记图到蛋白质结构域的摘要。然后，这些表征可以存储在诸如Pub-Chem或蛋白质数据库等数据库中，并经常被搜索，例如，用于蛋白质靶标的潜在小分子激动剂。重要的是，正如我们将在后面展开的，有趣的生物分子往往是稀疏的，非随机分布在许多表征空间中，这可以用于加速前面提到的搜索。
在研究比单一蛋白质或化合物更复杂的现象时，我们通常希望将事物综合起来，形成对生物学的系统层次的理解。为此，我们经常使用网络来表示生物数据，例如蛋白质之间的遗传和物理相互作用，以及代谢途径中的相互作用。3.虽然标准的网络科学工具已经被用于这些分析，例如，一些方法使用扩散或随机游走来探索网络的拓扑结构9，11它们通常与更具体的生物数据配对，如IsoRank所示32和IsoRankN21除了随机游走外，还使用保守生物函数进行全局多网络对齐。还有一些工具可以解决其他生物问题，比如猫鼬，10它分析代谢网络。然而，鉴于生物网络科学的广度，它超出了本文的范围。
生物数据的挑战
鉴于从NGS技术中读取的DNA或RNA，第一个任务是组装那些序列片段变成了连续的序列。组装问题类似于把一本书的所有页都撕下来重新构造的问题。新创装配超出了本文的范围，但由于序列被许多重叠的读取所覆盖，所以装配是可能的;3.对于这个任务，德布鲁因图数据结构是常用的。6然而，通常情况下，参考基因组(或在RNA的情况下，转录组)可用于被测序的生物体;建立人类参考基因组确实是人类基因组计划的目的。
当引用序列可用时，NGS读取可以映射到该引用(图2 c)．继续书的类比，当你有另一本(也许是不完美的)书的副本来匹配书页时，把一本书的所有书页都撕下来重建会容易得多。绘图允许新测序的基因组与待分析的参考基因之间的差异;这些差异或变异可能包括单核苷酸多态性(snp，它是位翻转的遗传类似物，见图2 b)，插入或删除，或基因组中更大规模的变化。确定个体基因组和参考基因组之间的差异被称为变异召唤。虽然基于引用的读取映射从根本上来说是一个比从头组装更简单的问题，但它在计算上仍然很复杂，因为每一个gb或tb的读取都必须映射到参考基因组上，其碱基对可能从数百万(细菌)到数十亿(哺乳动物)不等。例如ICGC-TCGA Pan Cancer全基因组分析(PCAWG)36汇集了来自约80个机构的500多名顶级癌症研究人员，目标是绘制37种常见癌症类型的整个突变景观。目前，即使是在机构连接下，下载每个样本也需要7个小时。重要的是，研究人员不相信提供的映射，因此他们重做映射。花在映射上的时间大约是花在序列分析管道上的总时间的50%。由于读映射通常是NGS分析管道中成本最高的步骤(例如，GATK)，对现有映射器的任何改进都将立即加速对大型读数据集的序列分析研究。
由于下一代测序的成本直线下降，1000基因组计划1正在追求人类变异的广泛目录;许多完整的基因组被编目，而不是为一个物种产生一个单一的参考基因组。同样的，WormBase和FlyBase正在为许多不同的物种和菌株编目秀丽蠕虫和果蝇分别是果蝇。这些基因组使跨物种推断成为可能，例如关于基因和调控区域，从而洞察功能和进化。3.同样，巨大的测序数据在存储、访问和分析方面存在问题。
在研究比单一蛋白质或化合物更复杂的现象时，我们通常希望将事物综合起来，形成对生物学的系统层次的理解。为此，我们经常使用网络来表示生物数据。
有了测序后的基因组，接下来自然会问哪些基因(编码蛋白质的基因组区域)存在，每个产生的蛋白质具有什么结构，以及它具有什么生物功能。识别可能的基因是一个经过充分研究的问题3.超出了本文的范围。然而，确定进化关系、结构和功能是当前计算生物学研究的核心。由于一些生物(称为生物模型)的研究比其他的更深入，而且众所周知进化会保存序列、结构和功能，确定这些属性的一个强有力的方法是寻找已知更多的相似序列。这种所谓的同源性搜索需要在数据库中搜索已知基因或蛋白质序列的近似匹配。先前认为同源搜索问题已经解决;基本本地对齐搜索工具(BLAST)3.已经成为在核苷酸和蛋白质序列数据库中进行同源性(相似性)搜索的标准工具。BLAST采用“播种和扩展”的方法;它看起来很小，k-mer匹配，这可能导致更长的匹配，并贪婪地扩展它们，最终在查询和每个潜在的数据库命中之间产生序列对齐。然而，BLAST的运行时间与被搜索数据库的大小成线性增长，这是有问题的，因为序列数据库的增长速度比摩尔定律更快。
潜在规模更大的是宏基因组数据。宏基因组学是对构成特定环境的许多基因组(细菌、真菌甚至病毒)的研究。这样的环境可能是来自特定地区的土壤(这可能导致新抗生素的发现)14)，也可能是人类肠道，肠道微生物群与人类健康问题有关，包括自闭症谱系障碍，23克罗恩氏病和肥胖。
宏基因组学从根本上问的是存在什么生物，以及在肠道等微生物组的情况下，它作为一个整体可以完成什么代谢功能。解决这个问题的一种方法是尝试将一个宏基因组样本的NGS reads映射到一组预期存在的参考基因组上。这正是前面讨论的读取映射问题，但是有许多参考基因组，增加了计算需求。第二种方法是在蛋白质序列数据库中进行同源搜索;精确或接近精确的匹配暗示着一个物种的存在，而更遥远的匹配可能仍能提供其功能的线索。对于这项任务，BLASTX2通常用于将核苷酸解读为它们可能的蛋白质序列，并在蛋白质数据库中搜索它们。困难之处就在于，要弄清这些问题所需的数据集，即“霰弹枪”宏基因组学数据集，规模庞大，比标准基因组数据集复杂得多。大量的数据导致对某些细菌、病毒、物种和属的鉴定面临重大挑战。19
基于化学结构和功能的药物及其靶标的计算研究被称为chemogenomics。5在药物发现和药物再利用领域，生物活性化合物的预测是一项重要的任务。计算高通量筛选消除了湿实验室中许多繁琐的化合物，但即使是计算筛选也很耗时。
化学基因组学通常依赖于比较化学图结构来识别相似的分子和结合位点。此外，比较化学图结构通常涉及计算最大公共子图(MCS)，这是一个np难题。然而，有越来越多的这样的化合物需要研究;NCBI的PubChem数据库已经从2011年1月的3100万种化合物增长到2015年7月的6800万种化合物。
存储、搜索和分析这些不断增长的数据集的持续能力取决于利用数据结构和冗余的聪明算法。事实上，这些不断增长的数据集“有可能使正在出现的问题在计算上变得不可行”。3.
应对这些挑战的最先进方法
基于引用的读映射技术通常依赖于诸如Burrows-Wheeler变换(BWT)这样的算法方法，BWT通过可逆转换提供高效的字符串压缩，而mf -index数据结构是基于BWT的压缩子字符串索引，它提供高效的存储和快速的搜索。3.BWA (Burrows-Wheeler Aligner)使用BWT，而Bowtie2mapper进一步依赖于fm索引来实现NGS读的高效映射。3.基因组多工具(GEM)绘图器24还在参考基因组的压缩表示中使用了与动态规划相结合的fm索引，以便在映射读取到参考基因组时精简搜索空间。马赛33和mrsFAST15使用“近似种子”方法索引可能匹配的空间，同样修剪搜索空间;然而，它的大部分运行时都花在扩展阶段。最先进的映射器mrsFAST-Ultra基于机器架构实现了效率的提高，而不是利用数据本身的冗余，具有近乎完美的灵敏度，但仅适用于没有插入和删除(indels)的情况。16即使有了这些方法，读映射仍然是基因组研究的一个重要瓶颈。3.
如果研究人员希望在未来应用更先进的绘图工具或其他分析，压缩读取以存储是必要的。4如前所述，NGS读取由序列字符串和相关的质量评分组成，后者在压缩时通常使用更多的空间。利用生物结构的优势，可以更好地压缩NGS读取的两个部分。与文献中其他一些压缩质量分数的方法不同，4，26石英39利用了中号的优势l-mers在许多情况下几乎可以唯一地识别基因组中的位置，限制了质量评分是有信息的可能性，并允许无信息评分的有损压缩。因为石英的有损压缩注入了分布的信息l-mers在目标基因组中，它证明了不仅改善了压缩比竞争方法，但轻微提高了下游变量调用的准确性。39类似地，对于读取的序列组件，Mince27利用序列冗余，将相似的读取(那些共享一个共同的short15bp子字符串)分组到桶中，允许删除该公共子字符串并将其作为桶标签处理，以便压缩表示中的每个读取只包含其与桶标签的惟一区别。这种方法允许通用压缩机实现更好的压缩。SCALCE3.也依赖于一个“增强”方案，重新排序读取，以这样一种方式，通用压缩机实现改进压缩。
宏基因组搜索工具的最新进展依赖于对BLASTX的两个改进:索引和字母精简。RapSearch240依赖于字母减少和无冲突哈希表。字母缩减，因为它是可逆的，可以被认为是一种无损压缩的形式;一个由20个字母组成的氨基酸字母表被映射到一个更小的字母表上，并存储偏移量以恢复完整字母表中的原始序列。哈希表提供了要搜索的数据库的有效索引。钻石7也依赖于字母简化，但本质上使用“形状种子”，k-长度为1524的mer，在912个特定位置使用通配符，而不是简单的k-mer seeds来索引数据库。DIAMOND的搜索性能比BLASTX快3到4个数量级，但在被搜索数据库的大小上仍然是线性的。
最近在基因表达方面的工作探索了利用数据高维结构的其他方法。表达式线性组合的稀疏恢复28带来了来自压缩感知的想法8到基因表达分析。另一种利用基因表达空间结构的新方法是parei(帕累托任务推理)，17它将一组数据描述为一个多面体，并从多面体顶点上最丰富的特征推断出该多面体顶点所代表的特定任务。
最广泛使用的化学基因组学搜索是小分子子图检测器(SMSD)，29它应用了基于相关图的大小和复杂性的MCS算法中的一种。值得注意的是，大型的化学化合物数据库，如PubCHEM，不能在笔记本电脑上使用现有的工具(如SMSD)进行搜索。
生物数据结构
幸运的是，生物数据具有独特的结构，我们稍后将利用该结构执行按数据库大小次线性扩展的搜索。38第一个关键的观察结果是，许多生物数据是高度冗余的;如果对一个人类基因组进行了计算，而研究人员希望对另一个人类基因组进行同样的计算，那么大部分工作已经完成了。22在处理冗余数据时，首先想到的是集群。虽然基于集群的搜索已经得到了很好的研究，20.传统智慧认为，它提供了一个恒定的因素加速穷尽搜索。
然而，除了冗余之外，大型生物数据集的另一个特征非常突出。存在的生物序列比可以列举的要少得多，但更重要的是，那些存在的生物序列往往与许多其他的高度相似。多亏了进化，只有那些表现出有用生物功能的基因才能存活下来，而大多数随机序列的氨基酸不可能形成稳定的结构。由于两个人类基因组的平均差异只有0.1%，1000个人类基因组的集合所包含的唯一信息还不到单个基因组的两倍。22因此，生物数据不仅表现出冗余，而且往往不会驻留在接近整个可行空间的任何地方(图3)．在这种情况下，进化的物理定律似乎将数据限制在笛卡尔空间的一个特定子空间中。
与冗余相关的一个关键洞见是，这样的数据集表现得很低度量熵。38也就是说，对于给定的集群半径rc还有一个数据库D，号码k需要覆盖的集群D受制于Nrc(D)，度规熵，与|相比相对较小D|，数据库中的条目数(图3)．相反，如果这些点在笛卡尔空间内均匀分布，Nrc(D)会更大。
第二个关键的洞见是生物数据集的分形维数很低。38也就是说，在一定半径范围内r1而且r2数据库中的任意一点D，分形维数d是
，在那里n1而且n2分数在多少r1而且r2分别为(图3)．
基于集群的搜索，例如“压缩组学”，使用压缩来加速分析，可以在半径内执行近似搜索r查询的问在数据库上D具有分形维数d还有度规熵k在规模上rc在时间上与
在哪里BD(q, r)为中的点的集合D包含在一个半径的球内r大概有一点q。
根据这种形式，比率
提供粗略搜索组件相对于完全线性搜索的加速因子的估计值。精细搜索的时间复杂度在分形维数上呈指数级d，可以通过在数据集上采样局部分形维数来全局估计。附表提供了分形维数d在典型查询半径采样，以及比率，用于核苷酸序列、蛋白质序列、蛋白质结构和化合物数据库。
生物数据集具有冗余性，并且受物理规律的约束，只存在于子空间中;也就是说，绝大多数可列举的序列和结构不存在，因为它们没有优势(或者至少，没有被进化所选择)。这种组合导致了较低的分形维数和较低的度量熵相对于数据集的大小，这表明“压缩组学”将提供计算能力，以次线性的方式扩展大量增长的数据。
压缩算法的时代
我们正在进入压缩算法的时代，它利用这种完全不同的范式来处理生物数据的结构。Loh, Baym和Berger试图利用基因组序列数据中固有的冗余性22介绍了压缩基因组学，一种依赖于压缩数据的方法，该方法可以在压缩的表示中执行所需的计算(如BLAST搜索)。压缩基因组学是基于压缩加速它依赖于两阶段搜索，简称为粗而且细搜索。粗搜索只对表示唯一数据的粗子序列或代表性子序列执行。在查询的某个阈值内的任何有代表性的序列，然后展开为它所代表的所有相似的序列;精细搜索是在原始数据库的这个(通常是很小的)子集上进行的。这种方法为BLAST核苷酸提供了数量级的运行时改进22和蛋白质12搜索;这些运行时改进随着数据库的增长而增加。
CORA读映射器37应用中等大小的l基于-mer的读取压缩方法，并提供参考基因组的压缩索引(称为同源表)。CORA，像caBLAST(压缩加速爆炸)22caBLASTP,12通过允许现有工具在压缩空间中操作，加速现有工具(在本例中，包括BWA或Bowtie2在内的读取映射器)，并依赖于粗阶段和细阶段。相比之下，短的种子聚类方案，如在马赛使用的那些33和MrsFAST，3与CORA在概念上的不同在于，这些方案仅旨在加速种子到引用的匹配步骤。因此，会有后续的种子扩展步骤，该步骤的成本要高得多，而且仍然需要对每个读取和映射单独执行，即使在对种子进行集群时也是如此。通过其l基于-mer的读压缩模型，CORA能够加速并实现在粗映射中的种子匹配和种子扩展步骤的渐近次线性缩放，这包含了读映射计算的主要部分。传统上,k-mers指长度固定的短子串(通常，但不一定是2的幂)，用作较长序列匹配的“种子”。CORA使用的时间更长k-mers(例如，3364个核苷酸长)，并在很小的Hamming或Levenshtein距离内将每个核苷酸与其相邻的核苷酸连接起来。这个词l-mer将这些子字符串与一般的短字符串区别开来k即。
在宏基因组搜索领域，最近发布了MICA38演示了caBLAST的压缩-加速方法22和caBLASTP12很大程度上与字母减少和索引方法正交。MICA将压缩-加速框架应用于最先进的DIAMOND，7使用它进行“粗搜索”阶段，用户选择DIAMOND或BLASTX进行“精搜索”阶段;与高度优化的DIAMOND相比，MICA的运行时间提高了近一个数量级，与caBLASTP相比BLASTP的运行时间提高相当。
压缩基因组学22已经推广并适应于非序列空间，并创造了“压缩组学”。化学基因组学就是这样一个例子。应用压缩加速方法，Ammolite38将PubChem数据库上的SMSD搜索平均提高150倍。另一个例子是esFragBag，38该软件基于蛋白质的词包向量的余弦距离或欧氏距离对蛋白质进行聚类，进一步将FragBag的运行时间平均提高了10倍。
在某些情况下，压缩组学方法可能以准确性为代价。然而，这些情况都有很好的定义。压缩组学从来不会导致假阳性(相对于naïve搜索技术正在加速)，因为精细搜索阶段对候选人应用与naïve方法相同的比较。此外，当用于比较的距离函数更具体地说是一个度规时，当它服从三角形不等式时，假阴性也不会发生。然而，在实践中，使用的是非度量距离函数，例如BLAST中的e值或esFragBag中的余弦距离，因此可能会出现假阴性。幸运的是，这些错误率很低，召回率超过90%。12，22，38
结论
生物数据的爆炸式增长，很大程度上是由于新一代测序等技术的进步，给我们带来了机遇和挑战。要想揭开癌症、肥胖、阿尔茨海默症、自闭症谱系障碍等疾病的秘密，以及更好地理解生物学的基础科学，就必须依靠研究人员分析不断增长的基因组、宏基因组、结构和交互组数据的能力。
压缩加速度的方法，22它可以根据数据的度量熵进行缩放，38虽然为许多其他有用的索引技术提供了正交优势，但它是处理海量数据的重要工具。将这种压缩加速方法扩展到宏基因组学，NGS读取映射，37化学基因组学表明了它的灵活性。同样地，这些应用的压缩存储可以显示为随数据集的信息理论熵的伸缩。38
计算生物学领域必须继续创新，但也必须吸收其他计算机科学领域的最佳想法。例如，压缩加速方法与度量球树相似，20多年前首次在数据库社区中描述;35然而，后者不允许人们根据度量熵和分形维数来分析性能保证。其他来自图像处理，计算几何，18sublinear-time算法,30.生物学以外的其他领域也有可能取得成果。在计算生物学中开发的算法思想也很可能在其他经历数据泛滥的领域变得有用，比如天文学或社交网络。34
生物数据科学之所以独特，主要有两个原因:生物学本身，甚至分子生物学都早于信息时代，以及“生物学中没有任何东西是有意义的，除非从进化的角度来看。”13生物学家不仅开发了各种各样的实验技术，而且数据来自于令人震惊的复杂过程，而这些过程本身是由进化驱动的。正是通过开发利用生物数据结构的算法，我们才能从进化的角度理解生物。
致谢
这项工作由美国国立卫生研究院支持，资助项目为GM108348。y.w.y也得到赫兹奖学金的支持。
参考文献
1.1000基因组计划联盟等。来自1092个人类基因组的遗传变异综合图谱。大自然491年， 7422(2012)， 5665。
2.Altschul, S.F, Gish, W, Miller, W, Myers, E.W.和Lipman, D.J.基本的局部对齐搜索工具。分子生物学杂志215， 3(1990)， 403410。
3.彭杰，彭杰，张文华。组学数据的计算解。自然评论遗传学14， 5(2013)， 333346。
4.FASTQ和SAM格式测序数据的压缩。PLoS ONE 8， 3 (2013)， e59190。
5.化学基因组学:快速靶点和药物发现的新兴策略。自然评论遗传学5， 4(2004)， 262275。
6.布鲁因，D.N.一个组合问题。在荷兰Akademie van Wetenschappen博物馆，A辑(1946)， 758。
7.Buchfink, B, Xie, C，和Huson, D.H.使用DIAMOND快速和敏感的蛋白质校准。自然方法12， 1(2015)， 5960。
8.坎迪斯，e。j。陶。t。线性规划解码。《IEEE信息理论汇刊， 12(2005)， 42034215。
9.Cao M, Zhang H, Park, J, Daniels, N.M, Crovella, M.E, Cowen, L.J.和Hescott, B.蛋白质功能预测的距离:蛋白质相互作用网络的一种新的距离度量。PLoS ONE 8， 10(2013)。
10.Chindelevitch, L.， Trigg, J.， Regev, a .和Berger, B.代谢网络模型一致性和可重复性结构分析的精确算法工具箱。自然通讯5,(2014)。
11.Cho, H.， Berger, B.，和Peng, J.扩散成分分析:解开生物网络中的功能拓扑。计算分子生物学研究“，”施普林格，2015,6264。
12.daniel, n.m.， Gallant, A, Peng, J, Cowen, l.j.， Baym, M.和Berger, M.用于蛋白质数据库的压缩基因组学。生物信息学29(2013), i283i290。
13.除非从进化论的角度来看，生物学中没有任何东西是有意义的(1973)。
14.福斯伯格，K.J.，雷耶斯，A.，王，B.， Selleck, E.M.， Sommer, M.O.和Dantas, G.土壤细菌和人类病原体的共同抗生素耐药组。科学337地球物理学报，6098(2012)，11071111。
15.Hach, F.， Hormozdiari, F.， Alkan, C.， Hormozdiari, F.， Birol, I.， Eichler, E.E.和Sahinalp, S.C. mrsFAST:一种用于短读映射的缓存无关算法。自然方法7， 8(2010)， 576577。
16.Hach, F.， Sarra, I. Hormozdiari, F.， Alkan, C.， Eichler, E.E.和Sahinalp, S.C. mrsFAST-Ultra:一种用于高性能测序应用的紧凑的snp感知映射器。核酸研究(2014), gku370。
17.Y.哈特，H.谢夫特，H.豪瑟，J.， Szekely, P.， Ben-Moshe, N.B.， Korem, Y.， Tendler, A.， Mayo, A.E.和Alon, U.利用高维数据的帕累托分析推断生物任务。自然方法12， 3(2015)， 233235。
18.Indyk, P.和Motwani, R.近似最近的邻居:朝着消除维度诅咒的方向。在十三届会议的议事录thACM计算理论年度研讨会。中国科学院学报，1998,604613。
19.Janda, J.M.和Abbott, S.L. 16S rRNA基因测序用于诊断实验室的细菌鉴定:优点，危险和缺陷。J.临床微生物学45， 9(2007)， 27612764。
20.Jardine, N.和van Rijsbergen, C.J.层次聚类在信息检索中的应用。信息存储与检索， 5(1971) 217240。
21.廖,c。，Lu, K., Baym, M., Singh, R. and Berger, B. IsoRankN: Spectral methods for global alignment of multiple protein networks.生物信息学12(2009), i253i258。
22.Loh, P.-R。，Baym, M., and Berger, B. Compressive genomics.自然生物技术30， 7(2012)， 627630。
23.肠道微生物群的短链脂肪酸发酵产物:在自闭症谱系障碍中的意义。健康与疾病中的微生物生态学(2012)。
24.Marco-Sola, S.， Sammeth, M.， Guigó， R.和Ribeca, P.宝石绘图器:通过过滤快速、准确和多功能校准。自然方法9， 12(2012)， 11851188。
25.生物学:大数据的巨大挑战。大自然498年， 7453(2013)， 255260。
26.奥乔亚，Asnani, H.， Bharadia, D.， Chowdhury, M.， Weissman, T.和Yona, G. QualComp:基于率失真理论的新的有损压缩器质量评分。生物信息学14， 1(2013)， 187。
27.Patro, R.和Kingsford, C.数据依赖桶改进了测序读取的无引用压缩。生物信息学(2015)。
28.Prat, Y.， Fromer, M.， Linial, N.和Linial, M.通过基因表达的稀疏表示恢复关键的生物成分。生物信息学5(2011), 655661。
29.S.A Rahman, Bashton, M, Holliday, g.l.， Schrader, R.和Thornton, J.M.小分子子图检测器(SMSD)工具包。J.化学信息学1， 1(2009)， 113。
30.鲁比菲尔德和夏皮拉，亚线性时间算法。离散数学25， 4(2011)， 15621588。
31.沙茨，m.c.，朗米德，B.和萨尔茨伯格，S.L.云计算和DNA数据竞赛。自然生物技术28， 7(2010)， 691693。
32.Singh R, Xu J.和Berger B.多蛋白质相互作用网络的全局对齐及其在功能矫形检测中的应用。在美国国家科学院院刊， 35(2008)， 1276312768。
33.Siragusa, E, Weese, D.和Reinert, K.具有近似种子和多次回溯的快速和准确的读取映射。核酸研究41， 7 (2013)， e78。
34.斯蒂芬斯，Z.D.等。大数据:天文数据还是基因组数据?13 .公共科学图书馆， 7 (2015)， e1002195。
35.用度量树满足一般的接近度/相似度查询。信息处理信件40， 4(1991)， 175179。
36.温斯坦，J.N.等人。癌症基因组图谱泛癌症分析项目。自然遗传学45， 10(2013)， 11131120。
37.于玉文，于玉文，彭杰，张晓燕。压缩映射在下一代测序中的应用自然生物技术4(2016), 374376。
38.余永伟，丹尼尔斯，丹科，华盛顿和伯杰，B.海量生物数据的熵尺度搜索。细胞系统1， 2(2015)， 130140。
39.Yu yw, Yorukoglu, D, Peng J.和Berger B.质量分数压缩提高了基因分型的准确性。自然生物技术33， 3(2015)， 240243。
40.RAPSearch2:用于下一代测序数据的快速和记忆效率高的蛋白质相似度搜索工具。生物信息学28， 1(2012)， 125126。
数据
图1。(a)摩尔定律和(b) Kryder定律与基因组序列数据对比。
图3。对任意高维空间中的点的卡通描绘，可能产生于进化过程中由突变和选择产生的基因组。
数字四个数据集在典型搜索半径下的度量熵比(聚类与数据库条目的比值)和分形维数。
数字观看作者在此独家讨论他们的工作通信视频。//www.eqigeno.com/videos/computational-biology-in-the-21st-century
数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.
评论
CACM管理员
以下信件发表在2016年11月出版的《致编辑的信》(//www.eqigeno.com/magazines/2016/11/209131)上。
——CACM管理员
Bonnie Berger等人的文章《21世纪的计算生物学:压缩算法缩放》(2016年8月)描述了现代生物学和医学研究如何从计算的密集使用中受益。微生物学已经成为数据丰富的;例如，序列数据(如DNA、RNA碱基串和蛋白质序列)的数量呈指数级增长，特别是自第三个千年之初对人类基因组进行初步测序以来。Berger等人指出，生物学家的生长指数甚至比摩尔定律还要大。这种增长导致越来越多的医学研究资金流向数据丰富的“组学”。但是摩尔定律使人们负担得起的和更大的医疗指数之间的区别从长远来看本身也是指数级的。Berger等人提出了更智能的算法来填补这一空白。
这篇文章描述了生物信息学对云计算的现成采用，但许多电子生物学的真正并行性质却没有说明;例如，Illumina下一代测序仪可以产生超过10亿个短DNA串，每一个都可以独立并行处理。高端图形硬件gpu已经包含了数千个处理核，提供的原始处理能力甚至比多核cpu都要高得多。因此，生物信息学转向gpu也就不足为奇了。
Berger等人确实提到了BWA对Burrows-Wheeler压缩转换的实现。BarraCUDA是BWA到英伟达硬件的成熟移植，针对现代gpu进行了优化;结果在2015年ACM遗传与进化计算会议上公布。(1)此外，Nvidia保留了许多在其并行硬件上运行的生物信息学应用程序和工具的列表。
在10多年前CPU时钟达到3GHz的峰值后，摩尔定律推动21世纪的计算实现了并行。如今，gpu和gpu风格的多核硬件处于领先的通用并行计算体系结构的中心。许多微生物学数据处理本质上是并行的。计算生物学和gpu是一个很好的匹配，并将继续共同发展。
b兰登
伦敦,英国
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
参考文献
(1)。兰登，W.B.等人。用遗传编程改进CUDA DNA分析软件。在2015年ACM遗传和进化计算会议论文集(马德里，西班牙，1115年7月)上发表。ACM出版社，纽约，2015,10631070。
显示1评论