在Python中聚类相似字符串的算法？

Question

我正在研究一个目前包含多个DNA序列列表的脚本（每个列表都有不同数量的DNA序列），我需要根据汉明距离相似性对每个列表中的序列进行聚类。我目前的实现（此时非常粗略）提取列表中的第一个序列并计算每个后续序列的汉明距离。如果它在某个汉明距离内，则将其附加到新列表中，该列表稍后用于从原始列表中删除序列以及将相似序列存储在defaultdict中。请参阅下面我的代码的当前实现：

def hamming_dist(sequence1, sequence2):
"""
Calculates the hamming distance between 2 sequences
"""
    assert len(sequence1) == len(sequence2)
    return sum(sequence1 !=sequence2 for sequence1,sequence2 \
    in itertools.izip(sequence1,sequence2))


def group_sequences(sequences_list):
    trash_sequences = []
    main_sequence = sequences_list[0]
    clustered_sequence = defaultdict(list)
    while len(sequences_list) > 1:
        for sequence in sequences_list:
            ham_dist = hamming_dist(main_sequence,sequence)
            if hamming_dist < 30:
                trash_sequences.append(sequence)

        for similar_sequences in trash_sequences:
            sequences_list.remove(similar_sequences)
            clustered_sequence[main_tcr].append(similar_sequences)
    else:
        clustered_sequence[main_sequence].append(None)
    return clustered_sequence

显然，这不是最好或最有效的方法，即使使用这个实现，我遇到的脚本中仍然存在一些错误。我仔细阅读了StackOverflow / StackExchange问​​题，看看其他人是否遇到了我的问题和我发现的类似问题，其他许多人都提到了使用算法，如K-Means算法，Markov聚类方法，层次聚类等。除了需要数字而不是字符串的K-means方法之外，我对这些方法中的任何一种都不太熟悉。

您建议我使用哪种聚类方法将相似的DNA序列聚类在一起，以及实施您首选方法的最佳方法？我们欢迎所有的建议！

Answer 1

入门的最佳选择是分层聚类。

它很容易理解，它允许任何距离，并且它可以将聚类可视化为树，即使数据本身很难可视化。