论文部分内容阅读
摘要：元基因组学是计算生物学领域的一个重要分支，主要研究环境中微生物群落的基因组。元基因组分类算法是用计算机程序对一个样本中的多个不同种属的微生物基因序列分离开来，以提供给生物学家进行深入研究的参考。元基因组分类算法主要分为两大类，一是基于同源性的分类，二是基于组成成分的分类。基于同源性分类主要利用序列的物种同源性信息，基于组成成分的分类方法通常提取序列的l-mer特征利用计算机科学领域的聚类方法，如k-means聚类。该文介绍基于组成成分的元基因组分类算法及其实例，并分析各实例算法的特点。最后总结并展望基于组成成分的元基因组算法当前方法及未来可以做的优化。
关键词：元基因组；组成成分；聚类算法
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）01-0135-02
1 生物背景
元基因组学亦称宏基因组学，是对微生物基因组的研究，是计算生物学领域的一个分支。计算生物学是利用现有的计算机科学相关先进技术（高性能计算机硬件，高效率算法，并行计算等）研究生物科学领域的相关问题的学科[1]。
元基因组分类算法是利用计算机通过微生物群落基因组序列数据分析该群落的物种结构。 这些微生物通常分布在土壤、深海、动物表皮及肠道等场所，对自然环境及动物、人体的健康有着重要的间接或直接关系。研究表明，人体肠道内的微生物群落结构发生异常时可导致IBD疾病（Inammatory Bowel Disease）[2]。
元基因组基因序列读段（reads）通常来自一个微生物群落的多个物种的基因片段，在元基因组的研究过程中，一个重要的步骤是对这些基因片段进行分组，即相近的物种的基因片段聚成一个类，亦称元基因组分类[3]，从而确定该生物群落中有哪些微生物。到目前为止，研究者们提出了多种计算生物学方法来对元基因组分类，主要分为两大类：一是基于同源性分类方法，二是基于组成成分分类方法。前一种需要用BLAST[4]对目标序列从参考（reference）基因数据库中匹配，找到最匹配的种属。由于BLAST用在序列对齐的操作上需要花费大量时间，此种方法相对而言效率较低。而且，这种方法较大依赖参考基因数据库，由于大部分微生物的基因组并不存在于该数据库中，所以对匹配的结果影响较大。但对于已知的微生物基因组，匹配得到的结果准确度较高。后一种方法无需参考基因数据库，通过提取基因组的l-mer特征，得到特征向量再用聚类方法进行聚类。该类方法不能找到基因组读段相对应的物种，但分类效率及准确度高。
2 基于组成成分的元基因组分类算法
AbundanceBin[5]、MetaCluster[6]、Mcluster[7]是三种基于组成成分对元基因组分类的算法代表。
AbundanceBin是印第安纳大学的研究者于2011年发表在 《计算生物学杂志》 （Journal of Computational Biology）上的一种分类算法。首先，文中假设基因组的序列读段服从兰德-沃特曼模型（Lander-Waterman model）[abudancebin29]，也就是每个序列中的碱基的位置服从泊松分布（Poisson distribution）。對于所有的基因组序列，可以认为是一个混合的泊松分布。对于给定的一个元基因组序列数据集，该算法首先计算每个序列l-mer的数量，然后用EM算法（Expectation-Maximization）预测出物种丰度和基因组的大小，最后得到每个序列对应的微生物的最后分组。文中对序列长度分别是400bp，75bp及方差分别为50，5的数据集做了实验，l-mer中的l值取20，结果表明该算法能在较短的时间里取得较高的分类准确度。
MetaCluster是香港大学王毅（音译WangYi）等人研究的对元基因分类的算法系列[8]。该系列算法从最初的MetaCluster2.0到2012年发表的MetaCluster5.0，能够分别处理不同序列长度、序列错误率的元基因组数据集。该文中谈及的MetaCluster主要指MetaCluster5.0。MetaCluster（MetaCluster5.0）算法对元基因组数据集分类主要分为两个过程。在第一个过程中，首先对元基因组数据集进行过滤，得到丰度较大的一组及丰度较小的一组。对丰度较大的一组进行l-mer特征提取，此时l取l=4。得到4-mer特征后，对这部分序列进行k-means聚类，得到相对较长的contig（聚类后得到的较长序列）。再对contig进行l-mer特征提取，此时l取l=5。得到contig的5元特征后，聚类后得到丰度较大的序列分类结果。在第二个过程中，完成第一步中过滤得到的丰度较小的一组序列数据聚类。对这些序列数据，首先进行合并来源于同一个长序列的短序列，然后再进行l-mer特征提取，l取l=4，再聚类得到两个过程的最后结果。文中在平均序列长度为75bp的模拟数据集及真实数据集上做了实验，表明MetaCluster在计算时间及内在耗用上有较大优势，并且对数据集中丰度不同序列有较好的分类效果。
Mcluster是复旦大学的研究者于2013年发表在《IEEE/ACM Transactions on computational biology and bioinformatics》上的算法。该算法提出了基于l-mer（l=4） 特征提取后自动权重迭代的思想。Mcluster首先提取数据集中序列的l-mer特征向量，然后随机初始化k个中心点，对所有特征设为一个相同的初始权重。接下来是两个需要迭代的步骤。I）计算每个特征向量每个维度相对于k个中心的距离，根据权重公式计算每个特征向量的新权重，并且将其归到距离最近的中心点所代表的聚类类簇。Ii）计算完所有的特征向量后，得到新的k个聚类类簇，再重新计算得到k个新的中心点。并且重新计算得到新的权重公式。重复迭代上述i）、ii）步骤，直到k个中心点达到稳定状态。该算法在多个模拟数据集及一个真实数据集上做了实验，并且和AbundanceBin、MetaCluster算法做了比较。实验结果的权衡标准主要基于三个数值，一是分类准确度，二是敏感度，三是F-measure（即准确度和敏感度的权衡值）。在上述三个标准中，Mcluster在模拟数据集及真实数据集中比AbundanceBin和MetaCluster算法都具有更理想的性能。 3 總结及展望
之前的分类算法大多数是基于同源性比较，主要用到BLAST序列匹对方法，需要耗费大量的时间和计算资源。AbundanceBin在基于组成成分的元基因组分类算法研究上具有开创性意义，它优化了分类的计算时间，并且指引了研究者可以在基于组成成分上进行研究元基因组分类。但AbundanceBin的缺点也比较明显，即当元基因组数据集中包含不同物种并且各物种不同丰度时，分类的效果欠佳。
MetaCluster的分类效果比AbundanceBin更佳，但其对元基因组数据集的要求是序列长度在50bp-128bp（MetaCluster5.0要求）之间，这也让MetaCluster（5.0）局限于处理较短长度的元基因组数据。MCluster处理的数据集序列长度在128bp-1000bp间，相比AbundanceBin及MetaCluster在准确率、敏感度、F-measure上都有较好的分类效果，是目前为止综合分类效果最佳的元基因组分类算法。
在未来对元基因组分类算法的研究上，有待完善及具有挑战性的有以下几点。
1） 能够处理较大范围的数据集序列长度。由于基因组测序技术的发展，目前多种平台的测序数据的长度在几十到几百几千bp的不等读段长度，若分类算法只能处理几十到几百的序列读段长度，则有局限性。
2） l-mer特征提取的l值自适应选取。4-mer特征提取在序列长度在500-1000bp时，具有较好的特征向量结果，但在序列长度为50-100时，特征向量的多数维度是无效的。并且在序列长度在2000bp以上时，5-mer特征提取能达到更高的准确度。按照数据集中平均的序列长度，选取相应的l值进行l元特征提取能够优化元基因组分类结果，是未来研究的一个方向。
总而言之，国内外基于组成成分的元基因组分类算法研究在这几年的研究中取得了一定的成就。在未来的研究中，也仍具有挑战性的难点等待研究者们去攻克。
参考文献：
[1] John C. Wooley， Adam Godzik， Iddo Friedberg. （2010）. A primer on metagenomics. Plos Computational Biology， Feb 2010， Vol 6， Issue 2， e1000667
[2] Qin J， Li R， Raes J， et al.A human gut microbial gene catalogue established by metagenomic sequencing. Nature， 2010（464）：7285.
[3] Mavromatis K， Ivanova N， Barry K， et al.Use of simulated data sets to evaluate the _delity of metagenomic processing methods. Nature Methods， 2007，4（6）：495-500.
[4] Scott McGinnis， Thomas L. Madden ： BLAST： at the core of a powerful and diverse set of sequence analysis tools， Nucleic Acids Research， 2004，32（20）.
[5] Wu Y， Ye Y.A novel abundance-based algorithm for binning metagenomic sequences using l-tuples. Journal of Computational Biology ， 2011，18（3）：523-534.
[6] Wang Y， Leung H C， Yiu S M， et al.Metacluster 5.0： a two-round binning approach for metagenomic data for low-abundance species in a noisy sample. Bioinformatics ， 2012，28（18）， 356-362.
[7] Liao R， Zhang R， Guan J， et al.A new unsupervised binning approach for metagenomic sequences based on n-grams and automatic feature weighting. IEEE/ACM Transactions on Computational Biology and Bioinformatics （TCBB） （2014）.
[8] http：//i.cs.hku.hk/～alse/MetaCluster/.
关键词：元基因组；组成成分；聚类算法
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）01-0135-02
1 生物背景
元基因组学亦称宏基因组学，是对微生物基因组的研究，是计算生物学领域的一个分支。计算生物学是利用现有的计算机科学相关先进技术（高性能计算机硬件，高效率算法，并行计算等）研究生物科学领域的相关问题的学科[1]。
元基因组分类算法是利用计算机通过微生物群落基因组序列数据分析该群落的物种结构。 这些微生物通常分布在土壤、深海、动物表皮及肠道等场所，对自然环境及动物、人体的健康有着重要的间接或直接关系。研究表明，人体肠道内的微生物群落结构发生异常时可导致IBD疾病（Inammatory Bowel Disease）[2]。
元基因组基因序列读段（reads）通常来自一个微生物群落的多个物种的基因片段，在元基因组的研究过程中，一个重要的步骤是对这些基因片段进行分组，即相近的物种的基因片段聚成一个类，亦称元基因组分类[3]，从而确定该生物群落中有哪些微生物。到目前为止，研究者们提出了多种计算生物学方法来对元基因组分类，主要分为两大类：一是基于同源性分类方法，二是基于组成成分分类方法。前一种需要用BLAST[4]对目标序列从参考（reference）基因数据库中匹配，找到最匹配的种属。由于BLAST用在序列对齐的操作上需要花费大量时间，此种方法相对而言效率较低。而且，这种方法较大依赖参考基因数据库，由于大部分微生物的基因组并不存在于该数据库中，所以对匹配的结果影响较大。但对于已知的微生物基因组，匹配得到的结果准确度较高。后一种方法无需参考基因数据库，通过提取基因组的l-mer特征，得到特征向量再用聚类方法进行聚类。该类方法不能找到基因组读段相对应的物种，但分类效率及准确度高。
2 基于组成成分的元基因组分类算法
AbundanceBin[5]、MetaCluster[6]、Mcluster[7]是三种基于组成成分对元基因组分类的算法代表。
AbundanceBin是印第安纳大学的研究者于2011年发表在 《计算生物学杂志》 （Journal of Computational Biology）上的一种分类算法。首先，文中假设基因组的序列读段服从兰德-沃特曼模型（Lander-Waterman model）[abudancebin29]，也就是每个序列中的碱基的位置服从泊松分布（Poisson distribution）。對于所有的基因组序列，可以认为是一个混合的泊松分布。对于给定的一个元基因组序列数据集，该算法首先计算每个序列l-mer的数量，然后用EM算法（Expectation-Maximization）预测出物种丰度和基因组的大小，最后得到每个序列对应的微生物的最后分组。文中对序列长度分别是400bp，75bp及方差分别为50，5的数据集做了实验，l-mer中的l值取20，结果表明该算法能在较短的时间里取得较高的分类准确度。
MetaCluster是香港大学王毅（音译WangYi）等人研究的对元基因分类的算法系列[8]。该系列算法从最初的MetaCluster2.0到2012年发表的MetaCluster5.0，能够分别处理不同序列长度、序列错误率的元基因组数据集。该文中谈及的MetaCluster主要指MetaCluster5.0。MetaCluster（MetaCluster5.0）算法对元基因组数据集分类主要分为两个过程。在第一个过程中，首先对元基因组数据集进行过滤，得到丰度较大的一组及丰度较小的一组。对丰度较大的一组进行l-mer特征提取，此时l取l=4。得到4-mer特征后，对这部分序列进行k-means聚类，得到相对较长的contig（聚类后得到的较长序列）。再对contig进行l-mer特征提取，此时l取l=5。得到contig的5元特征后，聚类后得到丰度较大的序列分类结果。在第二个过程中，完成第一步中过滤得到的丰度较小的一组序列数据聚类。对这些序列数据，首先进行合并来源于同一个长序列的短序列，然后再进行l-mer特征提取，l取l=4，再聚类得到两个过程的最后结果。文中在平均序列长度为75bp的模拟数据集及真实数据集上做了实验，表明MetaCluster在计算时间及内在耗用上有较大优势，并且对数据集中丰度不同序列有较好的分类效果。
Mcluster是复旦大学的研究者于2013年发表在《IEEE/ACM Transactions on computational biology and bioinformatics》上的算法。该算法提出了基于l-mer（l=4） 特征提取后自动权重迭代的思想。Mcluster首先提取数据集中序列的l-mer特征向量，然后随机初始化k个中心点，对所有特征设为一个相同的初始权重。接下来是两个需要迭代的步骤。I）计算每个特征向量每个维度相对于k个中心的距离，根据权重公式计算每个特征向量的新权重，并且将其归到距离最近的中心点所代表的聚类类簇。Ii）计算完所有的特征向量后，得到新的k个聚类类簇，再重新计算得到k个新的中心点。并且重新计算得到新的权重公式。重复迭代上述i）、ii）步骤，直到k个中心点达到稳定状态。该算法在多个模拟数据集及一个真实数据集上做了实验，并且和AbundanceBin、MetaCluster算法做了比较。实验结果的权衡标准主要基于三个数值，一是分类准确度，二是敏感度，三是F-measure（即准确度和敏感度的权衡值）。在上述三个标准中，Mcluster在模拟数据集及真实数据集中比AbundanceBin和MetaCluster算法都具有更理想的性能。 3 總结及展望
之前的分类算法大多数是基于同源性比较，主要用到BLAST序列匹对方法，需要耗费大量的时间和计算资源。AbundanceBin在基于组成成分的元基因组分类算法研究上具有开创性意义，它优化了分类的计算时间，并且指引了研究者可以在基于组成成分上进行研究元基因组分类。但AbundanceBin的缺点也比较明显，即当元基因组数据集中包含不同物种并且各物种不同丰度时，分类的效果欠佳。
MetaCluster的分类效果比AbundanceBin更佳，但其对元基因组数据集的要求是序列长度在50bp-128bp（MetaCluster5.0要求）之间，这也让MetaCluster（5.0）局限于处理较短长度的元基因组数据。MCluster处理的数据集序列长度在128bp-1000bp间，相比AbundanceBin及MetaCluster在准确率、敏感度、F-measure上都有较好的分类效果，是目前为止综合分类效果最佳的元基因组分类算法。
在未来对元基因组分类算法的研究上，有待完善及具有挑战性的有以下几点。
1） 能够处理较大范围的数据集序列长度。由于基因组测序技术的发展，目前多种平台的测序数据的长度在几十到几百几千bp的不等读段长度，若分类算法只能处理几十到几百的序列读段长度，则有局限性。
2） l-mer特征提取的l值自适应选取。4-mer特征提取在序列长度在500-1000bp时，具有较好的特征向量结果，但在序列长度为50-100时，特征向量的多数维度是无效的。并且在序列长度在2000bp以上时，5-mer特征提取能达到更高的准确度。按照数据集中平均的序列长度，选取相应的l值进行l元特征提取能够优化元基因组分类结果，是未来研究的一个方向。
总而言之，国内外基于组成成分的元基因组分类算法研究在这几年的研究中取得了一定的成就。在未来的研究中，也仍具有挑战性的难点等待研究者们去攻克。
参考文献：
[1] John C. Wooley， Adam Godzik， Iddo Friedberg. （2010）. A primer on metagenomics. Plos Computational Biology， Feb 2010， Vol 6， Issue 2， e1000667
[2] Qin J， Li R， Raes J， et al.A human gut microbial gene catalogue established by metagenomic sequencing. Nature， 2010（464）：7285.
[3] Mavromatis K， Ivanova N， Barry K， et al.Use of simulated data sets to evaluate the _delity of metagenomic processing methods. Nature Methods， 2007，4（6）：495-500.
[4] Scott McGinnis， Thomas L. Madden ： BLAST： at the core of a powerful and diverse set of sequence analysis tools， Nucleic Acids Research， 2004，32（20）.
[5] Wu Y， Ye Y.A novel abundance-based algorithm for binning metagenomic sequences using l-tuples. Journal of Computational Biology ， 2011，18（3）：523-534.
[6] Wang Y， Leung H C， Yiu S M， et al.Metacluster 5.0： a two-round binning approach for metagenomic data for low-abundance species in a noisy sample. Bioinformatics ， 2012，28（18）， 356-362.
[7] Liao R， Zhang R， Guan J， et al.A new unsupervised binning approach for metagenomic sequences based on n-grams and automatic feature weighting. IEEE/ACM Transactions on Computational Biology and Bioinformatics （TCBB） （2014）.
[8] http：//i.cs.hku.hk/～alse/MetaCluster/.