python - 比较大列表中的项目 - 查找长度相差 1 个字母的项目 - Python

Question

我正在寻找解决 Python 中一直困扰的问题。我有一个文件，有一列，其中包含大约。 6,000 行。对于每一行，每个项目都是唯一的(此文件经过过滤以从 40,000 行文件中删除重复项)。每行中的项目长度各不相同，其中一些项目的长度与其他项目的长度相同。

单行示例:

IGHV3-30/33rn-IGHJ4-CARDPSLSSMITFGGVIVTRGYFDYW

或者更多在第三个“-”之后使用制表符分隔的示例(第一部分不同):

IGHV3-23-IGHJ4  CAKDRGYTGYGVYFDYW
IGHV4-39-IGHJ4  CARHDILTGYSYYFDYW
IGHV3-23-IGHJ3  CAKSGGWYLSDAFDIW
IGHV4-39-IGHJ4  CARTGFGELGFDYW
IGHV1-2-IGHJ2   CARDSDYDWYFDLW
IGHV1-8-IGHJ3   CARGQTYYDILTGPSDAFDIW
IGHV4-39-IGHJ5  CARSTGDWFDPW
IGHV3-9-IGHJ3   CANVPIYSSSYDAFDIW
IGHV3-23-IGHJ4  CAKDWELYYFDYW
IGHV3-23-IGHJ4  CAKDRGYTGFGVYFDYW
IGHV4-39-IGHJ4  CARHLGYNNSWYPFDYW
IGHV1-2-IGHJ4   CAREGYNWNDEGRFDYW
IGHV3-23-IGHJ3  CAKSSGWYLSDAFDIW
IGHV4-39-IGHJ4  CARYLGYNSNWYPFDYW
IGHV3-23-IGHJ6  CAKEGCSSGCPYYYYGMDVW
IGHV3-23-IGHJ3  CAKWGPDAFDIW
IGHV3-11-IGHJ   CATSGGSP
IGHV3-11-IGHJ4  CARDGDGYNDYW
IGHV1-2-IGHJ4   CARRIGYSSGSEDYW
IGHV1-2-IGHJ4   CARDIAVPGHGDYW
IGHV6-1-IGHJ4   CASGGAVPGYYFDYW

在第一列中，有一些不同的项目。在第二列中，每个项目都是唯一的。第一列项目需要匹配，然后第二列项目需要按最小不匹配度 2 进行排序。 理想情况下，这对于 Levenshtein 模块来说是很好的，因为我可以放置最大值，但我需要两个字符串。有没有办法在单个列表中的每个项目上使用 Levenshtein？

我需要做的是打开这个文件(我认为首先按长度对其进行排序可能会有所帮助，但我不确定)。将所有项目按长度分组后，我需要将这些项目按相差 1 个字符的组进行排序(第三个“-”之前的字符串需要相同，其中“-”之后的字符串应仅相差 1 个字符.)

我认为我遇到的问题是生成一个适当的 for 循环来迭代项目长度。

我到目前为止的代码:

import sys
import os
import Levenshtein

inp = sys.argv[1] # Input file containing single column of items

with open(inp, "r") as f1:
        vj = [line.strip() for line in f1]

lengths = []
for k in vj:
        i = len(k)
        lengths.append(i)

lengths_sort = sorted(lengths, reverse = True)

uniq_len = []
for i in lengths_sort:
       if i not in uniq_len:
                uniq_len.append(i)

print uniq_len #For QC purposes

def get_new_list(strings, counts, outlist=[]):
        for s in strings:
                if len(s) == counts[0]:
                        outlist.append(s)
        return outlist

new_vj = get_new_list(vj, uniq_len, outlist=[])
print new_vj
ham = Levenshtein.hamming(new_vj[0], new_vj[1])
print ham

所以我正在寻找的输出很好，但尚未完成:

[46, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18]
46
['IGHV3-30/33rn-IGHJ4-CAKDPSLSSMITFGGVIVTRGYFDYW', 'IGHV3-30/33rn-IGHJ4-CARDPSLSSMITFGGVIVTRGYFDYW']
1

有两个长度为 46 的项目(巧合的是，第三个“-”之前的字符串是相同的；太好了)，并且两个字符串之间仅相差一个字符。

我的麻烦是，1.如何迭代 uniq_len 列表中的数字作为“字符串”列表中匹配长度的输入(请参阅代码中的函数)。 2. 我想为每个不同的长度创建一个新列表。 3. 如果每个新列表中有多个项目，则所有项目仅相差 1 个字符。

注意:“-”是使用 UNIX Paste -d- 命令创建的，其中包含 3 个文件，每个文件包含 1 列来创建此文件。将这些文件与\t 作为分隔符粘贴在一起以创建 3 列会更容易吗？

那么，打开文件，去掉行，然后可以匹配第一列、第二列，看看第三列是否有一个或多个字符不同？

感谢所有帮助。

Answer 1

更新:修改为处理可变数量的“id”子字段并将结果打印为单个字符串。请注意，几个测试用例被添加到输入的末尾，以使一些测试用例具有不同数量的前导字段组成 id(即 2 个而不是 3 个)。

我还重命名了num_mismatches()函数hamming_distance()，因为它就是这样。

使用以下输入:

IGHV3-23-IGHJ4-CAKDRGYTGYGVYFDYW
IGHV4-39-IGHJ4-CARHDILTGYSYYFDYW
IGHV3-23-IGHJ3-CAKSGGWYLSDAFDIW
IGHV4-39-IGHJ4-CARTGFGELGFDYW
IGHV1-2-IGHJ2-CARDSDYDWYFDLW
IGHV1-8-IGHJ3-CARGQTYYDILTGPSDAFDIW
IGHV4-39-IGHJ5-CARSTGDWFDPW
IGHV3-9-IGHJ3-CANVPIYSSSYDAFDIW
IGHV3-23-IGHJ4-CAKDWELYYFDYW
IGHV3-23-IGHJ4-CAKDRGYTGFGVYFDYW
IGHV4-39-IGHJ4-CARHLGYNNSWYPFDYW
IGHV1-2-IGHJ4-CAREGYNWNDEGRFDYW
IGHV3-23-IGHJ3-CAKSSGWYLSDAFDIW
IGHV4-39-IGHJ4-CARYLGYNSNWYPFDYW
IGHV3-23-IGHJ6-CAKEGCSSGCPYYYYGMDVW
IGHV3-23-IGHJ3-CAKWGPDAFDIW
IGHV3-11-IGHJ-CATSGGSP
IGHV3-11-IGHJ4-CARDGDGYNDYW
IGHV1-2-IGHJ4-CARRIGYSSGSEDYW
IGHV1-2-IGHJ4-CARDIAVPGHGDYW
IGHV6-1-IGHJ4-CASGGAVPGYYFDYW
IGHV1-2-CAREGYNWNDEGRFDYW
IGHV4-39-CARSTGDWFDPW
IGHV1-2-CARDSDYDWYFDLW

这个脚本:

from collections import defaultdict
from itertools import izip, tee
import os
import sys

# http://en.wikipedia.org/wiki/Hamming_distance#Algorithm_example
def hamming_distance(s1, s2):
    """ Count number of mismatched characters in equal length strings. """
    if not isinstance(s1, basestring): raise ValueError('s1 is not a string')
    if not isinstance(s2, basestring): raise ValueError('s2 is not a string')
    if len(s1) != len(s2): raise ValueError('string lengths do not match')
    return sum(a != b for a, b in izip(s1, s2))

def pairwise(iterable):  # itertools recipe
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

inp = sys.argv[1]  # Input file

unique = defaultdict(list)
with open(inp, 'rb') as file:
    for fields in (line.strip().split('-') for line in file):
        id = '-'.join(fields[:-1])  # recombine all but last field into an id
        unique[id].append(fields[-1])  # accumulate ending fields with same id

for id in sorted(unique):
    final_fields = unique[id]
    final_fields.sort(key=lambda field: len(field))  # sort by length
    print id + ':' + '-'.join(final_fields)
    if len(final_fields) > 1:  # at least one pair to compare for mismatches?
        for a, b in pairwise(final_fields):
            if len(a) == len(b) and hamming_distance(a, b) < 2:
                print '  {!r} and {!r} differ by < 2 characters'.format(a, b)

输出:

IGHV1-2:CARDSDYDWYFDLW-CAREGYNWNDEGRFDYW
IGHV1-2-IGHJ2:CARDSDYDWYFDLW
IGHV1-2-IGHJ4:CARDIAVPGHGDYW-CARRIGYSSGSEDYW-CAREGYNWNDEGRFDYW
IGHV1-8-IGHJ3:CARGQTYYDILTGPSDAFDIW
IGHV3-11-IGHJ:CATSGGSP
IGHV3-11-IGHJ4:CARDGDGYNDYW
IGHV3-23-IGHJ3:CAKWGPDAFDIW-CAKSGGWYLSDAFDIW-CAKSSGWYLSDAFDIW
  'CAKSGGWYLSDAFDIW' and 'CAKSSGWYLSDAFDIW' differ by < 2 characters
IGHV3-23-IGHJ4:CAKDWELYYFDYW-CAKDRGYTGYGVYFDYW-CAKDRGYTGFGVYFDYW
  'CAKDRGYTGYGVYFDYW' and 'CAKDRGYTGFGVYFDYW' differ by < 2 characters
IGHV3-23-IGHJ6:CAKEGCSSGCPYYYYGMDVW
IGHV3-9-IGHJ3:CANVPIYSSSYDAFDIW
IGHV4-39:CARSTGDWFDPW
IGHV4-39-IGHJ4:CARTGFGELGFDYW-CARHDILTGYSYYFDYW-CARHLGYNNSWYPFDYW-CARYLGYNSNWYPFDYW
IGHV4-39-IGHJ5:CARSTGDWFDPW
IGHV6-1-IGHJ4:CASGGAVPGYYFDYW

希望此更新也能有所帮助...