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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

Я предполагаю, что у вас есть один 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 |).

Answer 4

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

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

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

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