Повышение эффективности построения матрицы перекрытия строк

У меня есть огромный список (N = ~ 1 миллион) строк длиной 100 символов, между которыми я пытаюсь найти совпадения. Например, одна строка может быть

XXXXXXXXXXXXXXXXXXAACTGCXAACTGGAAXA (and so on)

Мне нужно построить матрицу N на N, которая содержит самое длинное значение перекрытия для каждой строки с каждой другой строкой. Мой текущий метод (псевдокод)

читать все строки в массив

создать пустую матрицу NxN

сравнить каждую строку с каждой строкой с более высоким индексом массива (чтобы избежать повторного сравнения)

Запишите самое длинное перекрытие в матрицу

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

Если вы не догадались, это фрагменты ДНК. X обозначает «подстановочный знак» (зонд дал значение ниже порогового показателя качества), а все остальные параметры являются базовыми (A, C, T или G). Я пытался написать алгоритм четвертичного дерева, но этот метод был слишком ресурсоемким.

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

Редактировать: некоторые выдержки из кода, которые иллюстрируют мой текущий метод. Все, что не имеет отношения к концепции, было удалено

//part that compares them all to each other
for (int j=0; j<counter; j++) //counter holds # of DNA
for (int k=j+1; k<counter; k++)
int test = determineBestOverlap(DNArray[j],DNArray[k]);

//boring stuff

//part that compares strings. Definitely very inefficient,
//although I think the sheer number of comparisons is the main problem
int determineBestOverlap(string str1, string str2)
{
int maxCounter = 0, bestOffset = 0;
//basically just tries overlapping the strings every possible way
for (int j=0; j<str2.length(); j++)
{
int counter = 0, offset = 0;
while (str1[offset] == str2[j+offset] && str1[offset] != 'X')
{
counter++;
offset++;
}

if (counter > maxCounter)
{
maxCounter = counter;
bestOffset = j;
}
}
return maxCounter;
} //this simplified version doesn't account for flipped strings

2

Решение

Вы действительно должны знать соответствие между ВСЕМИ парами строк? Если да, то вам придется сравнивать каждую строку с каждой другой строкой, что означает, что вам понадобится n ^ 2/2 сравнений, и вам потребуется половина терабайта памяти, даже если вы просто храните один байт на пару строк.

Тем не менее, я предполагаю, что вы действительно заинтересованы в длинных строках, которые содержат, скажем, более 20 или 30 или даже более 80 общих символов, и вы, вероятно, не очень хотите знать, имеют ли две пары строк 3 общие символы, в то время как 50 других — X, а остальные 47 не совпадают.

Что бы я попробовал на вашем месте — все еще не зная, подходит ли это вашему приложению — это:

1) Из каждой строки извлеките самые большие подстроки, которые имеют смысл. Я предполагаю, что вы хотите полностью игнорировать ‘X’ в начале и в конце, и если некоторые «читаемые» части разбиты большим количеством «X», вероятно, имеет смысл обрабатывать читаемые части по отдельности вместо использования длинная строка Многое из этого «какие подстроки актуальны?» зависит от ваших данных и приложения, которые я действительно не знаю.

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

AGCGCTXATCG 1
GAGXTGACCTG 2
.....
CGCXTATC    1
......

3) Теперь сверху вниз по списку:

а) Установите «текущую строку» на строку, самую верхнюю в списке.

б) Если число вхождений рядом с текущей строкой> 1, вы нашли совпадение. Найдите в исходных строках подстроку, если вы не помните индексы, и отметьте совпадение.

c) Сравните текущую строку со всеми строками одинаковой длины, чтобы найти совпадения, где некоторые символы являются X.

г) Удалить 1-й символ из текущей строки. Если полученная строка уже находится в вашей таблице, увеличьте ее счетчик вхождений на единицу, иначе введите ее в таблицу.

e) Повторите 3b с последним, вместо первого, символом, удаленным из текущей строки.

е) Удалить текущую строку из списка.

ж) Повторяйте с 3а) до тех пор, пока у вас не закончится вычислительное время, или пока оставшиеся строки не станут слишком короткими, чтобы быть интересными.

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

1

Другие решения

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

Единственное, что я вижу, как это улучшить — это сравнение строк само по себе: заменить A, C, T, G и X на двоичные шаблоны:

  • A = 0x01
  • C = 0x02
  • T = 0x04
  • G = 0x08
  • X = 0x0F

Таким образом, вы можете сохранить один элемент на 4 бита, то есть два на байт (хотя это может быть не очень хорошая идея, но все же возможный вариант для исследования), а затем быстро сравнить их с операцией AND, так что вы «просто» нужно посчитать, сколько последовательных ненулевых значений у вас есть. Это просто способ обработки подстановочного знака, извините, у меня нет лучшей идеи уменьшить сложность общего сравнения.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector