生信黑板报之Mash

Mash发表在今年6月Genome Biology的上面，它借用MinHash这样一个搜索引擎常用的判断重复文档的技术而实现，另外增加了计算两两之间突变距离和P值显著性检验。Mash通过把大的序列集合简化成小的sketch，从而快速计算它们之间的广义突变距离（global mutation distances，可以近似地理解为『进化距离』，越大表示两者之间亲缘关系越近，如果是0，表示同一物种）。

关于它的应用，作者在文中列举了三个：

对NCBI RefSeq全部54,118个物种基因组做聚类（得到一个物种数据库sketch database），耗时33 CPU h

使用不同平台测序数据（拼接好的和未拼接的）实时搜索sketch database

对数千种宏基因组样本做聚类

Mash的原理，看这一张图就够了。首先把两个序列集合打碎成固定长度的短片段，称为k-mer，然后把每个k-mer经哈希函数转换成哈希值，就得到A和B两个由哈希值组成的集合，这样计算A、B两个序列集相似度的问题就转化成A、B两个集合的运算。Jaccard index就是A和B共有元素与A、B总元素之比，如果A和B是两个亲缘关系很远的物种，那么它们相似的序列就少，可以预期Jaccard index会比较小。这里做了一个近似，S(A U B)是集合A U B的一个随机抽样子集，用它代表A U B。

细心的读者可能注意到了，以上的计算中做了一个随机抽样的近似，这也是Mash可以大大节省资源消耗的一个关键，不难推论，抽样的群体越大，得到的估计值越接近真实值，遗憾的是，这样耗时也会相应增加，文章的实验结论也印证了这一点。

作者依据Mash建立的数据库，做了一个灵长类动物的进化树，这和用多序列比对结果得到的树基本一致。Mash的应用除了文章举的例子，还有很多，比如怀疑某个样本标错了，Mash一下很快知道；或者有的时候做比较转录组分析，选多序列比对的物种时，为到底用哪个物种做内参，哪个做外参纠结不已，也可以用它试试。

再说一下开头提出的，微信怎么判断公众号文章是否原创的问题。我不知道有没有人像我一样对这个问题好奇，网上查过，几乎没有这方面的文章，关于微信公众号抄袭现象的报道倒是有不少。事实上，公众号上面关于『如何自学生物信息学？』的文章，目前看到的都是从我的知乎抄过去的，不同的是有的扭扭捏捏的加了一个『来自知乎』，有的干脆大大方方的署上自己的单位。最逗的是，有一个公司账号，公众号里发完，又跑去自家论坛安利了一遍。

话说回来，到底要怎么检测雷同文章呢？类似前文提到的sketch database，要判断文章是否雷同，首先要有一个参考库，这个参考就是目前有原创认证的公号。把纳入原创公号池的所有文章进行索引，然后当新的公号文章发布时，会拿新文章到公号池文章库进行搜索，如果相似度较高，则强制设为转载并提示用户。

参考文献：Mash: fast genome and metagenome distance estimation using MinHashMash程序：https://github.com/marbl/mash

本文同步发布于知乎和微信公众号JackTalk