确定字符串位置的算法？

Question

我有两组字符串-每组大约5000个字符串-（更具体地说，序列只包含ACTG），它们根据一些其他数据分为两组。每根弦的长度都是相等的，效率并不重要。给定一个特定的序列，我希望能够确定该字符串属于哪一类*。我应该用什么算法来做这个？你知道吗

*完全基于各组先前的数据。你知道吗

一个小例子：

第1组：AATTGG
第2组：ATCCGC

如果我有字符串CCGTCC，它会转到第2组，因为第2组有更多的C序列，而第1组更喜欢A、T和G的两倍

Answer 1

这个问题没有确定下来。没有好的答案。但你还是被要求这么做。那是真实的生活。你知道吗

所以你有选择。学习很多关于机器学习的知识。那会让你做些聪明的事。或者做最愚蠢的事情，然后看看你是否喜欢结果。你知道吗

根据对你问题的描述，我建议采取以下方法。从当前的数据中构造“预测器”，预测下一个角色应该出现。就拿那些预测结果最好的人来说。你知道吗

那么什么样的预测因子呢？我建议使用ngrams和拉普拉斯平滑（每个看不见的答案加一个）。这很容易实现，而且在实践中可以很好地处理DNA数据。然后你可以做一些事情，比如0克（只是字母频率），1克（基于前一个字母），2克（前两个字母）和3克。你知道吗

对于每个预测器和每个可以预测的字母，您可以构建该预测器给出该字母的可能性的日志。加上日志，最后一个可能性最大的就是赢家。（添加日志在数学上相当于乘以概率，但可以避免超出浮点范围。）

你的例子太小了，不能说明这项技术的真正威力。没有足够的数据来训练1克、2克和3克。（对于1克，没有XY序列，出现了两次，因此由于拉普拉斯平滑，所有答案在任何观察到的X之后都被认为是同等可能的。对于2克和3克，用XY和XYZ替换X。）

然而，0-gram将给A、G和T组1 2/7的可能性，但只给C组1/7的可能性（第7个字符是C的假观察值，它实际上没有出现在字符串中-这是拉普拉斯平滑）对于测试字符串，这将给2*log(2/7) + 4* log(1/7) = -10.289166533212。相比之下，A、G和T的可能性为2 1/6，而C的可能性为1/2。这就给出了2*log(1/6) + 4*log(1/2) = -6.35610766069589因为第2组的预测因子做得更好，所以将其分配给第2组。你知道吗

请注意，此技术得到了您希望应用的推理的预期结果。第2组有更多的Cs，因此包含大量Cs的新字符串被分配给第2组。如果你有更多的数据，并且你所描述的模式继续有效，第一组会得到A，G和T的双倍值

另外请注意，给定大量字符串，此技术将学习可以用单个字母和短串的频率来描述的模式。但它不会去研究其他可能存在的模式。例如，如果第一组和第二组的起始字符是一个非常强的信号，你不会注意到。其他技术也可以。你知道吗

下面是此技术的代码：

import math
n_limit = 4

def make_predictor (strings):
    freq_dict = {}
    for string in strings:
        for i in range(len(string)):
            for j in range(n_limit): # 0..3
                if j <= i:
                    substr = string[i-j:i]
                    if substr not in freq_dict:
                        freq_dict[substr] = {}
                    freq = freq_dict[substr]
                    char = string[i]
                    if char not in freq:
                        freq[char] = 1.0
                    else:
                        freq[char] = freq[char] + 1.0

    # Smoothing and precalculation of logs.
    predict_dict = {}
    for substr, freq in freq_dict.iteritems():
        for char in 'ACGT':
            if char not in freq:
                freq[char] = 1.0
        total = sum(freq.values())
        predict = {}
        for char, f in freq.iteritems():
            predict[char] = math.log(f / total)
        predict_dict[substr] = predict

    return predict_dict

def run_predictor (predict_dict, string):
    answer = 0.0
    empty_predict = math.log(0.25) # 4 values, equally likely.
    for i in range(len(string)):
        for j in range(n_limit):
            if j <= i:
                substr = string[i-j:i]
                if substr not in predict_dict:
                    answer = answer + empty_predict
                else:
                    answer = answer + predict_dict[substr][string[i]]
    return answer

def classify (p1, p2, string):
    if run_predictor(p1, string) < run_predictor(p2, string):
        return 2
    else:
        return 1

predictor1 = make_predictor(['AATTGG'])
predictor2 = make_predictor(['ATCCGC'])

print(classify(predictor1, predictor2, 'CCGTCC'))

现在来测试一下，我建议把你的小组随机分成1A、1B、2A、2B组。如果1A和2A生成的预测因子能成功地将1B和2B组的东西分为1组和2组，那么这项技术可能对你的数据很有用。你知道吗