算法帮助!使用其伙伴搜索字符串的快速算法

Question

我正在寻找一种用于搜索目的的快速算法,这是一个巨大的字符串(它是一个由数亿到数十亿个字符组成的生物基因组序列).

该字符串中只有4个字符{A,C,G,T},"A"只能与"T"配对,而"C"与"G"配对.

现在我正在寻找两个子串({minLen,maxLen}之间的子串的长度约束,以及{intervalMinLen,intervalMaxLen}之间的间隔长度),它们可以反平行地相互配对.

例如,字符串是:ATCAG GACCA TACGC CTGAT

约束:minLen = 4,maxLen = 5,intervalMinLen = 9,intervalMaxLen = 10

结果应该是

1. "ATCAG"配对"CTGAT"

2. "TCAG"配对"CTGA"

提前致谢.

更新:我已经有了确定两个字符串是否可以相互配对的方法.唯一的问题是进行详尽的搜索是非常耗时的.

Answer 1

我认为这是一个有趣的问题，所以我编写了一个基于考虑“折叠”的程序，该程序从不同的“折叠点”向外扫描可能的对称匹配。如果 N 是核苷酸数量，M 是“maxInterval-minInterval”，则运行时间应该为 O(N*M)。我可能错过了一些边界情况，因此请小心使用代码，但它确实适用于提供的示例。请注意，我使用了填充的中间缓冲区来存储基因组，因为这减少了内部循环中所需的边界情况的比较次数；这会牺牲额外的内存分配以获得更好的速度。如果您进行任何更正或改进，请随时编辑该帖子。

class Program
{
    public sealed class Pairing
    {
        public int Index { get; private set; }

        public int Length { get; private set; }

        public int Offset { get; private set; }

        public Pairing(int index, int length, int offset)
        {
            Index = index;
            Length = length;
            Offset = offset;
        }
    }

    public static IEnumerable<Pairing> FindPairings(string genome, int minLen, int maxLen, int intervalMinLen, int intervalMaxLen)
    {
        int n = genome.Length;
        var padding = new string((char)0, maxLen);
        var padded = string.Concat(padding, genome, padding);

        int start = (intervalMinLen + minLen)/2 + maxLen;
        int end = n - (intervalMinLen + minLen)/2 + maxLen;

        //Consider 'fold locations' along the genome
        for (int i=start; i<end; i++)
        {
            //Consider 'odd' folding (centered on index) about index i
            int k = (intervalMinLen+2)/2;
            int maxK = (intervalMaxLen + 2)/2;
            while (k<=maxK)
            {
                int matchLength = 0;
                while (IsPaired(padded[i - k], padded[i + k]) && (k <= (maxK+maxLen)))
                {
                    matchLength++;

                    if (matchLength >= minLen && matchLength <= maxLen)
                    {
                        yield return new Pairing(i-k - maxLen, matchLength, 2*k - (matchLength-1));
                    }
                    k++;
                }
                k++;
            }

            //Consider 'even' folding (centered before index) about index i
            k = (intervalMinLen+1)/2;
            while (k <= maxK)
            {
                int matchLength = 0;
                while (IsPaired(padded[i - (k+1)], padded[i + k]) && (k<=maxK+maxLen))
                {
                    matchLength++;

                    if (matchLength >= minLen && matchLength <= maxLen)
                    {
                        yield return new Pairing(i - (k+1) - maxLen, matchLength, 2*k + 1 - (matchLength-1));
                    }
                    k++;
                }
                k++;
            }
        }
    }

    private const int SumAT = 'A' + 'T';
    private const int SumGC = 'G' + 'C';
    private static bool IsPaired(char a, char b)
    {
        return (a + b) == SumAT || (a + b) == SumGC;
    }


    static void Main(string[] args)
    {
        string genome = "ATCAGGACCATACGCCTGAT";
        foreach (var pairing in FindPairings(genome, 4, 5, 9, 10))
        {
            Console.WriteLine("'{0}' pair with '{1}'",
                              genome.Substring(pairing.Index, pairing.Length),
                              genome.Substring(pairing.Index + pairing.Offset, pairing.Length));
        }
        Console.ReadKey();
    }


}