Вычислите наибольшее расстояние между любыми двумя строками в группе, используя Python

Вы также можете попробовать использовать SequenceMatcher difflib из стандартной библиотеки:

>>> import difflib
>>> from itertools import groupby, combinations

>>> def find_max_ratio(lines):
    lines = [row.split() for row in lines]  # the file should already break at each line break
    lines = [(int(row[0]), row[1]) for row in lines]
    lines = groupby(sorted(lines), lambda x: x[0])  # combine strings into their respective groups, sorting them first on int of first element
    group_max = dict()
    for group in lines:
        strings = list(group[1])  # need to convert group[1] from iterator into list
        if len(strings) > 1:  # if the number of strings is 1, then there is nothing to compare the string with in its group
            similarity = 1
            for line1, line2 in combinations(strings, 2):
                s = difflib.SequenceMatcher(None, line1[1], line2[1])  # need to compare second element in each list and exclude the first element (which is the group number)
                similarity = s.ratio() if s.ratio() < similarity else similarity
            group_max[line1[0]] = 1 - similarity  # gives difference ratio
    return group_max

>>> t = open('test.txt')
>>> print find_max_ratio(t)  # it appears that your examples don't have any differences
{'1': 0, '0': 0, '2': 0}

Затем вы можете рассчитать среднее значение следующим образом:

>>> max_ratios = find_max_ratio(t)
>>> average = sum(max_ratios.values())/float(len(max_ratios))
>>> average
0.0  # there are no differences in your test data above

EDIT: запись в файл

>>> output = sorted(max_ratios.items(), key=lambda x: x[1], reverse=True)  # sorting by descending ratios
>>> with open('test2.txt', 'w') as f:  # a new file name
>>>     f.write('\n'.join([group + ': ' + str(ratio) for group, ratio in output])
                + '\n\nAverage: ' + str(average))

РЕДАКТИРОВАНИЕ 2: Добавление минимальной разницы

Вы можете добавить минимальную разницу в свой результат (здесь в виде кортежа (<max_difference>, <min_difference>) вот так:

def find_maxmin_ratios(lines):
    lines = [row.split() for row in lines]  # the file should already break at each line break
    lines = [(int(row[0]), row[1]) for row in lines]
    lines = groupby(sorted(lines), lambda x: x[0])  # combine strings into their respective groups, sorting them first on int of first element
    group_minmax = dict()
    for index, group in lines:
        strings = list(group)  # need to convert group[1] from iterator into list
        if len(strings) > 1:  # if the number of strings is 1, then there is nothing to compare the string with in its group
            max_similarity = 1
            min_similarity = 0
            for line1, line2 in combinations(strings, 2):
                s = difflib.SequenceMatcher(None, line1[1], line2[1])  # need to compare second element in each list and exclude the first element (which is the group number)
                max_similarity = s.ratio() if s.ratio() < max_similarity else max_similarity
                min_similarity = s.ratio() if s.ratio() > min_similarity else min_similarity
            group_minmax[index] = (1 - max_similarity, 1 - min_similarity)  # gives max difference ratio and then min difference ratio
    return group_minmax

Затем вы можете найти соответствующие средние значения следующим образом:

>>> t = open('test.txt')
>>> maxmin_ratios = find_maxmin_ratios(t)
>>> maxmin_ratios
{'1': (0, 0.0), '0': (0, 0.0), '2': (0, 0.0)}  # again, no differences in your test data
>>> average_max = sum([maxmin[0] for maxmin in maxmin_ratios.values()])/float(len(maxmin_ratios))
>>> average_min = sum([maxmin[1] for maxmin in maxmin_ratios.values()])/float(len(maxmin_ratios))
>>> average_max, average_min
(0.0, 0.0)  # no differences in your test data

Правка 3. Проблемы с оптимизацией

Наконец, в свете вашего последнего комментария, я не уверен, что вы сможете слишком оптимизировать эту функцию в ее нынешнем виде. Если ваш компьютер не может с этим справиться, вам может потребоваться обработать небольшие фрагменты текста, а затем скомпилировать результаты в конце. difflib не требует огромных объемов памяти, но делает МНОГО работы. Ваша производительность ДОЛЖНА быть намного лучше моей (в зависимости от вашей машины), потому что каждая моя строка была случайной. Если ваши линии больше похожи, чем различны, вы должны сделать намного лучше. Вот результаты cProfile на моей машине для следующего сценария (всего 3,172 часа):

text2.txt
- 9700 lines of text
- each line begins with one random number (1 to 10)
- each line has 400 random characters that follow the random number  # if your data is not random, you should do CONSIDERABLY better than this

Обратите внимание, что большая часть cumtime (общее время для данной функции и всех функций ниже нее) было потрачено в difflib, что вне вашего контроля с текущей функцией. На самом деле остальная часть функции занимает совсем немного времени.

4581938093 function calls in 11422.852 seconds

   Ordered by: tottime  # the total time spent in a given function, excluding time spent in subfunctions

ncalls  tottime percall cumtime percall filename:lineno(function)
81770876    8579.568    0   9919.636    0   difflib.py:350(find_longest_match)
-724102230  1268.238    0   1268.238    0   {method 'get' of 'dict' objects}
4700900 874.878 0   1143.419    0   difflib.py:306(__chain_b)
9401960 160.366 0   10183.511   0.001   difflib.py:460(get_matching_blocks)
2060343126  141.242 0   141.242 0   {method 'append' of 'list' objects}
1889761800  110.013 0   110.013 0   {method 'setdefault' of 'dict' objects}
81770876    32.433  0   55.41   0   <string>:8(__new__)
130877001   32.061  0   32.061  0   {built-in method  __new__ of type object at 0x1E228030}
81770876    29.773  0   29.773  0   {method 'pop' of 'list' objects}
1   23.259  23.259  11422.852   11422.852   <pyshell#50>:1(find_maxmin_ratios)
49106125    21.45   0   33.218  0   <string>:12(_make)
9401960 20.539  0   10239.234   0.001   difflib.py:636(ratio)
335752019   17.719  0   17.719  0   {len}
9401960 17.607  0   30.829  0   {_functools.reduce}
4700900 16.778  0   49.996  0   {map}
230344786   16.42   0   16.42   0   {method  __contains__' of 'set' objects}
191093877   14.962  0   14.962  0   {method 'add' of 'set' objects}
98214517    13.222  0   13.222  0   difflib.py:658(<lambda>)
4700900 6.428   0   6.428   0   {method 'sort' of 'list' objects}
4700900 5.794   0   5.794   0   {method 'items' of 'dict' objects}
4700900 5.339   0   1148.758    0   difflib.py:261(set_seq2)
4700900 4.333   0   1160.351    0   difflib.py:154(__init__)
4700900 3.83    0   1156.018    0   difflib.py:223(set_seqs)
4700900 3.43    0   3.43    0   difflib.py:235(set_seq1)
9401960 3.162   0   3.162   0   difflib.py:41(_calculate_ratio)
9700    0.003   0   0.003   0   {method 'strip' of 'str' objects}
1   0.003   0.003   0.003   0.003   {sorted}
9700    0.001   0   0.001   0   <pyshell#50>:3(<lambda>)
1   0   0   11422.852   11422.852   <string>:1(<module>)
1   0   0   0   0   {method 'disable' of '_lsprof.Profiler' objects}

Если ваша машина может с этим справиться, я бы просто запустил эту функцию и был бы готов ждать два или три часа. Здесь происходит МНОГО всего, чтобы сравнивать эти строки посимвольно.

seq_file = open("sequences.txt", 'r')

# make an dict of groups, each group is a list of sequences in that group

groups = {}

for item in seq_file.readlines():
    (group, sequence) = item.split()
    try:
        groups[group].append(sequence)
    except:
        groups[group] = [sequence]

# measure the distance from every seq in a group to every other seq in that group,
# keep a record of the maximum found in each group.  (It doesn't matter that we 
# compare a sequence to itself during this process).

max_distances = {}
for group_num, group_seqs in groups.iteritems():
    greatest_distance = 0
    for seq in group_seqs:
        for other_seq in group_seqs:
            greatest_distance = max(greatest_distance, levenshtein_distance(seq, other_seq))

    max_distances[group_num] = greatest_distance          
    print "max for group %s is %s" % (group_num, greatest_distance)

# Average maximum distance, across the groups

max_distanace_list = max_distances.values()
av_max_dist = float(sum(max_distanace_list)/len(max_distanace_list))

... предоставленная вами ссылка показывает, как сделать levenshtein_distance().

Вы можете рассчитать процентную разницу между двумя строками следующим образом:

a="GCAUGC"
b="GCAACC"

differences=0

for i in xrange(len(a)):
    if a[i]!=b[i]:
         differences+=1

percentageDifference = 100 * float(difference)/len(a)

Это предполагает, что длины строк одинаковы, как и в вашем примере.

Теперь это зависит от того, что вы действительно подразумеваете под процентной разницей между всеми строками в группе, что вы хотите сделать. Например, вы можете иметь в виду, что хотите проверить разницу между каждой комбинацией двух строк в группе и получить среднее значение.

Проблема выполнения этого только для каждой группы может быть решена путем предварительной обработки данных. Если данные такие, как вы их показываете, вы можете разделить каждую строку в пространстве и использовать номер группы в качестве ключа в словаре и добавить строку в список, который является элементом. Что-то типа:

groupDictionary = {}

groupStringPair = line.split()
group = groupStringPair[0]
stringToAdd = groupStringPair[1]

try:
    groupDictionary[group].append(stringToAdd)
except KeyError:
    groupDictionary[group] = [stringToAdd]

Тогда у вас будет словарь с ключами для каждой группы и список строк для каждой группы в качестве элементов. Если вы хотите игнорировать группы, содержащие только одну строку, вы можете либо удалить их из словаря, либо игнорировать. Вы можете сделать это:

for k, v in groupDictionary.items():
    if len(v)==1:
        del groupDictionary[v]