Алгоритм помогите! Быстрый алгоритм поиска строки с партнером

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

Я знаю, что вы не ищете подстроки, но я думаю, что было бы целесообразно создать обратную строку генома, содержащую совпадения;Задача состоит в том, чтобы найти общие подстроки в двух строках.

Пример:

Исходная строка

  ATCAG GACCA TACGC CTGAT

Перевернутая строка:

  TAGTC CGCAT ACCAG GACTA

Если затем преобразовать строку в значения ее сопряжения (замените T<-> A и C <-> G, вы получаете что-то полезное:

  ATCAG GCGTA TGGTC CTGAT

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

Когда исходная строка и строка с обратным поиском, я думаю, ваша проблема звучит удивительно похоже на ' самая длинная общая подстрока 'проблема, которая хорошо описана. Ваша вторая предварительная обработка будет состоять в создании дерева суффиксов для быстрого поиска подстрок.

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

Answer 2

Метод описан в http://www.ncbi.nlm.nih.gov/pubmed/11381028

Genome Res. 2001 Jun; 11 (6): 1005-17. Сегментные дубликаты: организация и влияние в рамках текущего проекта генома человека сборка.

Answer 3

Самым простым решением было бы построить Trie из данных максимальной высоты maxLen.Каждый узел должен также иметь список местоположений, в которых была найдена эта конкретная строка (она будет в порядке возрастания, если дерево будет создано по порядку).

Затем, во время поиска, просто отмените дополнение строки поиска ипройти через три.Когда вы найдете совпадение, проверьте, находится ли одно из совпадений в надлежащем интервале, если «да», выведите строки.

Дайте мне знать, если вам нужен подробный алгоритм.

Answer 4

Я подумал, что это интересная проблема, поэтому я собрал программу, основанную на рассмотрении «складываний», которая сканирует наружу на предмет возможных симметричных совпадений из разных «точек сгиба». Если 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();
    }


}

Answer 5

Я бы посоветовал преобразовать строки в двоичную 16-битную длину:

A = 101
T = 010
C = 110
G = 001

Это позволяет использовать до 5 символов на 16-битную единицу.Это должно быть очень быстро по сравнению с поиском и сравнением строк.

Используйте верхний бит, чтобы определить, является ли это 4-последовательная единица или 5-последовательная единица.

Теперь вы можете выполнить быструю сортировку и получитьвсе 4 последовательности и 5 единиц последовательности в свои собственные группы (если только вам не нужно найти 4 единицы последовательности, которые частично совпадают с 5 единицами последовательности).

Для сравнения вы можете снова отсортировать, и вы обнаружите, чтовсе последовательности, начинающиеся с G, будут предшествовать последовательностям, начинающимся с T, затем A, а затем C. Затем вы можете взять последовательность и сравнить ее только с теми частями отсортированного массива, которые возможны - что должно быть намного, намного короче.Проблемное пространство.

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

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