Python-从数据集中删除高度相似的字符串

Question

我有一个基因组数据集包含基本消息,如下所示:

位置samp1 samp2 samp2 samp3 samp4 samp5 samp6 ...
posA TTTTTTT ...
posB GAAGGAA ...
posC GGGGGGG
......

该文件有100000多行,每行包含200个样本的200个碱基.
现在我想删除每个样本中具有高相似基数的位置,下面的图片是100%相同的,我将删除其中一个

我们定义了类似的比率(相似的基数)/(序列长度):

posH
CCCCCCCC posi ACCCACCC

posH和posI的相似度是6/8 = 75%根据需要,高于99%的类似比率被认为是高度相似的,并且去除了一个相似的位置.

我怎样才能有效地在python中完成这项工作？谢谢.

Answer 1

的相似性6/8之间的posH和posI,看起来像你想归的反汉明距离(即1-d).

您可以使用以下方法计算两个序列之间的反归一化汉明距离:

def inverse_hamming_distance(a,b):
    z = list(zip(a, b))
    return sum(e[0]==e[1] for e in z) / len(z)

它给出了:

>>> inverse_hamming_distance('CCCCCCCC', 'ACCCACCC')
0.75

但是,您可以通过尽早检测到两条线路不相似来节省一些CPU周期.给定最小相似度阈值t,如果您观察到int(0.5+(1-t)*len(z))不同的项目,则不需要直到最后,并且您已经可以告诉项目不相似.

def similar(a,b,t=0.99):
    l = min(len(a), len(b))
    t = int(0.5 + l*(1 - t))
    n = 0
    for a1, b1 in zip(a, b):
        if a1 != b1:
            n += 1
        if n > t:
            return False
    return True

测试:

>>> similar('CCCCCCCC', 'ACCCACCC', 0.75)
True
>>> similar('CCCCCCCC', 'ACCCACCC', 0.9)
False