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

Question

Мне нужно сравнить последовательности ДНК X и Y хромосом и найти закономерности (состоящие из 50-75 пар оснований), которые уникальны для Y-хромосомы.Обратите внимание, что эти части последовательности могут повторяться в хромосоме.Это должно быть сделано быстро (BLAST занимает 47 дней, нужно несколько часов или меньше).Существуют ли какие-либо алгоритмы или программы, особенно подходящие для такого сравнения?Опять же, здесь ключевым является скорость.

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

Answer 1

1. Построить дерево суффиксов S на последовательности X.
2. Для каждой начальной позиции i в последовательности Y ищите строку Y [i..i + 75] в S. Если не удается найти совпадения, начиная с позиции i (т. Е. Если поиск не удастся после сопоставления j <75 нуклеотидов) тогда вы нашли строку длины j, уникальную для Y. </li>
3. Наименьшая такая строка из всех начальных позиций i является самой короткой уникальной строкой (или просто остановитесь после того, как найдете любую такую ​​строку, если вы не заинтересованы в минимизации длины).

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

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

Answer 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 непосредственно перед диапазоном X, вы можете определить количество символов префикса между этим Y и всеми X по очереди, уменьшая секцию, выполняя операцию min на каждом шаге.Точно так же вы можете определить количество символов префикса, совместно используемых всеми этими символами X и Y, которые появляются следующим в массиве суффиксов, по цене одной минуты на X. То же самое, конечно, для диапазонов Y.Теперь сделайте максимум для каждой записи, чтобы определить самый длинный префикс, общий для каждой позиции в X (или Y) и любой позиции в Y (или X).

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

Answer 3

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

Answer 4

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

Следующим шагом является написание программы для графического процессора, возможно, с помощью Pixel Shader или Cuda или OpenCL

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

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