Быстрые алгоритмы поиска уникальных множеств в двух очень длинных последовательностях текста

Ответ 1

• Создайте дерево суффикс дерева S в последовательности X.
• Для каждой начальной позиции я в последовательности Y найдите строку Y [i..i + 75] в S. Если совпадение не может быть найдено, начиная с позиции я (т.е. если поиск не завершится после соответствия j < 75 нуклеотидов), то вы нашли строку length-j, уникальную для Y.
• Самая маленькая такая строка над всеми начальными позициями я является самой короткой уникальной строкой (или просто останавливается после того, как вы найдете какую-либо такую ​​строку, если вы не заинтересованы в минимизации длины).

Общее время: O (| X | + m | Y |), где m - максимальная длина строки (например, m = 75).

Есть, вероятно, еще более эффективные алгоритмы, основанные на обобщенных деревьях суффиксов.

Ответ 2

Я предполагаю, что у вас есть один X и один Y для сравнения. Объедините их, разделенные символом маркера, который не появляется ни в одном, чтобы сформировать, например. XoY. Теперь сформируйте http://en.wikipedia.org/wiki/Suffix_array в линейном времени.

То, что вы получаете, представляет собой массив указателей на позиции в конкатенированной строке, где указатели расположены так, что подстроки, на которые они указывают, отображаются в алфавитном порядке в массиве. Вы также получаете массив LCP, предоставляя длину самого длинного общего префикса, совместно используемого между суффиксом и суффиксом, непосредственно перед ним в массиве, который является суффиксом, который сортируется меньше, чем он. На самом деле это самый длинный общий префикс, разделяемый между этой позицией, и ЛЮБАЯ подстрока меньше, чем это, потому что все с более длинным общим префиксом и меньше строки [i] будет сортировать между ним и текущей строкой [i-1].

Вы можете указать, какая из исходных строк указатель указывает на ее позицию, потому что X до Y. Вы можете вырезать массив на чередующиеся подразделы указателей X и Y. Длина общего префикса, разделяемого между pos [i] и pos [i-1], равна lcp [i]. Длина префикса, разделяемого между pos [i] и pos [i-2], равна min (lcp [i], lcp [i-1]). Поэтому, если вы начинаете с значения Y непосредственно перед диапазоном Xs, вы можете выработать количество символов префикса между этим Y и всеми Xs в свою очередь, отступив в раздел, выполнив минимальную операцию на каждом шаге. Аналогичным образом вы можете определить количество символов префикса, разделяемых между всеми этими Xs и Y, которое появляется далее в массиве суффиксов, за одну минуту на X. То же самое, конечно, для диапазонов Y. Теперь сделайте максимум для каждой записи, чтобы выработать самый длинный префикс, разделяемый между каждой позицией в X (или Y) и любой позиции в Y (или X).

Я думаю, вы хотите, чтобы подстроки внутри X или Y имели небольшие префиксы, разделяемые между ним и любой другой подстрокой другого пола, потому что строки одного символа дольше, чем это, начиная с той же позиции, не отображаются в другом полу вообще. Я думаю, как только вы выполнили вычисления min() выше, вы можете извлечь N наименьших префиксных подстрок, используя кучу, чтобы отслеживать N наименьших записей. Я думаю, что все здесь занимает время, линейное в | X | + | Y | (если N не сравнимо с | X | или | Y |).

Ответ 3

Эта бумага может иметь некоторые альтернативы для адаптации BLAST для улучшения ее производительности (путем разделения разделителей проблемного пространства AFAIKS).

Ответ 4

У меня есть интересный ответ, это будет технологический. Основная идея заключается в том, что сравнение подпоследовательностей должно выполняться на графическом процессоре, поскольку графические процессоры современных видеокарт - это среда с высокой параллельной обработкой (например, небольшой суперкомпьютер). Таким образом, мы можем кодировать базовую пару как один пиксель, учитывая, что Х-хромосома составляет 154 миллиона пар - мы получаем изображение для Х-хромосомы, которое состоит из 154 миллионов пикселей - размер этого изображения будет около 500 МБ. Для Y-хромосомы мы получаем изображение размером 160 МБ. Таким образом, эти два (500 + 160) МБ изображений могут быть обработаны спусками видеокарты очень эффективно. (Просто получите видеокарту s >= 1 ГБ видеопамяти).

Следующий шаг - написать программу GPU, возможно, с помощью Pixel Shader или Cuda или OpenCL

Программа GPU была бы простой - в основном она будет сравнивать 50-75 соседних пикселей в изображении Y-хромосомы со всеми пикселями изображения Х-хромосомы. Таким образом, эта программа GPU должна иметь максимум 75 * 154 миллиона операций, которые будут вычисляться на современном графическом процессоре в течение часа или около того. Поскольку все подпоследовательности Y будут проверяться параллельно.

надеюсь, что поможет