代码之家 › 专栏 › 技术社区 › boyang

如何使用字符串的切片计算字符串中给定字符的概率?

bioinformatics probability string

boyang · 技术社区 · 10 年前

给定字符串,例如 01001010101001101011 ,我们可以随机切片多个子字符串。假设在切片过程中,由于一些意外的噪声,一些字符可能会翻转( 0->1 或 1->0 ). 例如:

Position: 0123456789.........
String:   01001010101001101011

slice1:    1001110101000
slice2:       1010111001111
slice3:       10101
slice4:                1101011

slice1 从位置1开始(假设字符串的索引以0开始), slice2 从位置4开始, slice3 从4开始,以及 slice4 从13开始。在里面 切片1 , 0 翻转到 1 在位置5和 1. 翻转到 0 在位置13。

对于原始字符串中的一个特定位置,如果是 1. ,则翻转到 0 在切片中为0.1;反之亦然(即。 Prob(0->1)=0.1 ).

问题是: 如果我们只有多个切片(每个切片的长度可能不同)及其在字符串中的起始位置,并且我们不知道原始字符串,给定原始字符串中的任意位置,我们如何计算位置为 1. ?

假设大多数位置将在切片中至少覆盖一次,我们有以下参数:

p01=0.1; // Probability a â0â in string but flipped to a â1â in a slice
p10=0.1; // Probability a â1â in string but flipped to a â0â in a slice
p1=0.5;  // Prior probability that any given position in string is a â1â

我们还可以假设字符串是一个0和1的随机字符串,在切片期间,每个位置都是独立采样的。

对于上面的示例字符串和四个切片,每个位置的概率如下:

我花了几个小时试图找出如何得到以上答案,我可以数出 0 s和 1. 在所有切片中,每个位置都有一个程序。然而,我仍然找不到公式或模型或算法计算概率,尤其是位置4( 1,1,1 ), 5( 1,0,0 ), 9( 0,1 ), 13( 0,1,1 ).

1 回复 | 直到 10 年前

aviator Martin York 10 年前

对于字符串中的每个位置,我们有 n 比特量(来自切片的信息)。让我们说 k 其中有“1”。

在你的例子中,在位置5,我们有n=3和k=1。

找到概率 p 如果原始字符串在该位置包含“1”,我们将使用 binomial distribution 。我们首先需要找到原始字符串中的“0”产生k=1的概率,如果n=3(因此1个1和2个0)。在这种情况下: 0.243 然后我们需要如果n=3,则a‘1’将产生k=1的概率。这是 0.027 。现在我们终于有了原始字符串中为“1”的概率:p=0.027/(0.243+0.027)= 0.1

我假设你可以自己获得n和k(每个位置)。C#或Java代码:

private float p1 = 0.5;
private float p01 = 0.1;
private float p10 = 0.1;

private float probItsOne(int n, int k)
{
    if (n == 0)
        return p1;
    float probByZero = binomial(n, p01, k); // probability a '0' would generate this k, given n
    float probByOne = binomial(n, p10, n - k);
    return probByOne / (probByZero + probByOne);
}

// (this p is not the same as in my explanation)
private float binomial(int n, float p, int k)
{
    return combinations(n, k) * Math.Pow(p, k) * Math.Pow(1 - p, n - k);
}

private int combinations(int n, int k)
{
    return (int)(factorial(n) / (factorial(k) * factorial(n - k));
}

private long factorial(int n)
{
    long result = 1;
    for (int i = 2; i <= n; n++)
        result *= i;
    return result;
}