计算两组或者N组特征数据的overlap以及覆盖度

这是生物信息学中诸多基本问题之一！

 

1 问题描述

 

（1 有一个序列，称为目标序列（ 类似一个很长的字符串，比如200M长），我们不关心它的字符集（指组成序列的所有字符的集合），只关心它的长度，以及下文提到的特征数据。

（2 特征数据：指序列上描述某种业务相关特征的一组区间。比如一个很小的例子，序列长为1000，有一组特征数据可能如下：[50,130],[200,300],[550,899]  ；其中每一个区间[start,end]表示序列上一个从start到end的片段。

（3 特征数据的特点： 一般情况下，要求特征数据的N个之间相互没有交叉或者重叠（self-overlap,inter-self）；一组特征数据一般覆盖整个序列的一部分，而不是全部。

（4 两组特征数据：指有两组 （2 中所描述的特征数据， 它们之间没有任何直接的关系

（5 多组特征数据：类似于（4 。

（6 覆盖度：一组特征数据的覆盖度是指：该组特征数据的所有区间对整个序列的覆盖程度，即区间的总长占序列总长的百分比；

（7 overlap ：指两组或多组特征数据，同时覆盖到的序列长度！

 

2 求解目标

 

（1 求一组特征数据的覆盖度：其实这个小学生都会， ，只是需要累加一下所有区间的长度而已；

（2 求两组特征数据的overlap ： 这个目标有两个子目标，一是要精确求出两组特征数据的overlap的大小，也就是这两组特征数据同时覆盖到的序列的长度，二是要精确给出overlap到底是哪些部分，即同时被两组特征数据覆盖到的序列上的片段（给出它们的起始和终止坐标，相当于得到第三组特征数据）；

（3 目标（2 的推广，要求多组特征数据的overlap ！！！

 

3 算法概述

 

（1 最小学生，也是最奢侈的算法就是：两重或者多重循环，逐对地去做区间比较，然后统计给出结果。这种方式首先浪费内存，从而空间效率低下；时间：O(n1 x n2 x n3 x ......) ； 但是，它有一个优点，那就是可以用来验证精确性；

 

（2 对于两组的特征数据，可以采用同时遍历两个数组的方式：先对两个组数据排序，然后设两个索引i,j,分别比较d[i] d[j]区间的起始，这种算法的时间：O(n1+n2) ，缺点是对于多组特征数据，处理起来很复杂，几乎不可实施；

 

（3 把两组数据标记起始和终止后，合并，排序；然后用一个缓冲的数组或者hash，在扫描排序后的数据时，逐个检查标志位，起始则放入hash,终止则以此和hash中的起始坐标相比，根据需求记录overlap信息。

 

（4 其他，比如内存映射法等。。。

 

 

4 附言：

 

这是我在工作中遇到的一个问题，曾经像网友悬赏求助，但并没有非常理想的结果。上述算法3是做组装的同事最常用的，因为他们经常要面对一个序列的多组特征数据，而且那些数据一般都是全覆盖目标序列。

 

之所以提出这个问题，是因为我们的目标序列一般都很长，不是100，1000，一般在1M以上；如果处理得是人类的基因组数据，那么这个目标序列一般是人的染色体，长度从250M到50M不等。 如果处理的是全基因组序列，那么一般为500M到3G甚至5G ！！！

 

所以，关键的问题是：

（1 算法要节省使用内存；

（2 算法要省时；没人愿意为了得到一个overlap而等一整天；

（3 算法封装要灵活，可以处理两组特征数据，也可以处理多组；

（4 算法要绝对精确，且附有准确性检验程序；

（5 如果您打算包装成一个优秀的程序，那么要规范，从测试数据到测试报告，从功能测试到性能测试。。。不管是文档还是用户指南。。。

 

如果您可以把此问题进一步抽象到更高层次，欢迎与我交流：nodexy AT gmai . com

 

实现方式：

（1 标准C

（2 主流脚本语言：SHELL相关,awk...；perl ；python；ruby ...；

（3 函数式语言：仍选

（4 Java

（5 其他

 

 

欢迎有兴趣者一同交流！！！