Решение, необходимое для идентификации частично совпадающих строк (последовательностей ДНК) в data.frame со многими строками - PullRequest
Новая
       22

Решение, необходимое для идентификации частично совпадающих строк (последовательностей ДНК) в data.frame со многими строками

4 голосов
/ 28 апреля 2020

Я ищу решение для следующей проблемы:

У меня есть фрейм данных с более чем 6 миллионами строк, который содержит информацию о последовательности (последовательность ДНК) в одной строке. В зависимости от способа представления набора данных в кадре данных будут дублироваться строки. НО: эти дубликаты не являются идеальными совпадениями . Позвольте мне показать это на примере. 

row 1: ATCTCAGCATCATACCAACTACTA
...
row 5: ATCTCAGCATCATA..........

Предыдущий блок показывает две последовательности в двух разных строках фрейма данных. Точки показаны только для целей визуализации (они не являются частью набора данных).

Цель: пометить эти последовательности как идентичные . (В конце моей целью является присвоение идентификатора последовательности каждой строке, поэтому эти две строки должны иметь одинаковый идентификатор последовательности, поскольку последовательность в строке 5 является частью последовательности в строке 1, и, следовательно, последовательности потенциально идентичны.

Я пытался использовать match функцию базового R или некоторые попытки с grep, но все эти подходы очень и очень медленные, если вообще не срабатывают.

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

(сообщение об ошибке от Biostring.) 

Error in .Call2("ACtree2_build", tb, pp_exclude, base_codes, nodebuf_ptr,  : 
  element 2 in Trusted Band has a different length than first element

У кого-нибудь есть идеи, как добиться того, чего я хочу достичь? Опять-таки, проблема заключается в размер фрейма данных с более чем 6 миллионами строк и в основном тестирование каждой строки для каждой строки в фрейме данных.

Большое спасибо за любые отзывы! Это действительно приветствуется!

ДОПОЛНЕНИЕ ИНФОРМАЦИИ Возможен ли способ, если верно следующее предположение: Это интересно только, когда строки совпадают в начале, и хотя бы одна строка должна соответствовать с полной последовательностью символов. Другими словами: полная последовательность одной строки может быть найдена в начале строки символов в одной или нескольких разных строках.

1 Ответ

2 голосов
/ 01 мая 2020

Вот кое-что, что я собрал для облегчения задачи (поиск последовательностей, которые являются начальной подстрокой других последовательностей). Более общая проблема может быть решена аналогичным образом, она просто сложнее и займет (намного) больше времени. На следующем шаге я планирую смоделировать ваши данные (создать текстовый файл с шестью миллионами строк в указанном вами диапазоне) и протестировать решение, чтобы узнать, сколько времени это займет. Затем, как я сказал, я попробую то же самое в Oracle базе данных, чтобы увидеть, есть ли огромная разница. «Общая проблема» - это разумный проект, только если «простая проблема» выполняется за разумное время.

Я предполагаю, что у данных есть какой-то идентификатор последовательности (идентификатор был бы естественным в базе данных). Вы увидите это во входном файле, который я покажу ниже. Вы также увидите формат вывода - для каждой более короткой последовательности, которая является начальной подстрокой более длинной, я показываю обе последовательности (и их идентификаторы). ПРИМЕЧАНИЕ. - более короткая последовательность, такая как ACTAG C, может быть начальной подстрокой нескольких более длинных строк, таких как ACTAGCTA и ACTAGCAGCA. Мой вывод показывает только одну более длинную последовательность, а не все более длинные последовательности.

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

С n последовательностями длиной не более k, упорядочение всех из них в алфавитном порядке - O(kn log n), а проверка каждой строки против следующей - O(kn) - вот почему это имеет шанс поработать над вашими 6 миллионами строк.

ВХОДНОЙ ФАЙЛ: 

$ cat input_file
10010 ACATAAGAGTGATGATAGATAGATGCAGATGACAGATG
10011 ATAGAGATGAGACAGATGACAGAAGATAGATAGAGCAGATAG
10013 ATAGAGTAGAGAGAGAGTACAGATAGAGGAGAGAGATAGAC
10015 ACAGATAGCAGATAGACAGA
10016 ACAGATGACAGAAGATAGATAGA
10018 TAAGAGTGATGATAGATAGATGCAGA
10023 ATCACCGTTACAGATCG
10024 GTGATGATAGATAGATGCAGATGACAGATG
10025 ATAGAGTAGAGAGAGAGT
10030 TAAGAGTGATGATAGATAG
10044 TAAGAGTGATGATAGATAGATGCAATGA

РЕДАКТИРОВАТЬ - BASH СЦЕНАРИЙ НИЖЕ ДОВОЛЬНО МОЗГ-МЕРТВ , Извиняюсь перед всеми. В конце этого ответа я покажу правильный способ сделать это; ИСПОЛЬЗУЯ SED, НЕ SHELL L OOP И ЧИТАЙТЕ КОМАНДУ

BASH SCRIPT Имя файла: dupes.sh

#!/bin/bash
sort -k 2 input_file | 
{
    read key1 seq1
    while read key2 seq2
    do
        if [[ $(expr substr $seq2 1 ${#seq1}) == $seq1 ]]
        then
            echo ""
            echo "$key1 $seq1"
            echo "$key2 $seq2"
        fi  
        key1=$key2
        seq1=$seq2
    done
}

(я использовал echo для вывода; вы, вероятно, захотите вместо этого перенаправить в файл.)

ПРИВЕДЕНИЕ И ВЫХОД 

$ ./dupes.sh

10025 ATAGAGTAGAGAGAGAGT
10013 ATAGAGTAGAGAGAGAGTACAGATAGAGGAGAGAGATAGAC

10030 TAAGAGTGATGATAGATAG
10044 TAAGAGTGATGATAGATAGATGCAATGA

РЕДАКТИРОВАТЬ - КАК Я СКАЗАЛ ВЫШЕ , Пока это правильный ответ, решение ужасно. Вот правильный способ сделать это в bash. Это решение занимает менее минуты (!!) для того же объема входных данных (а не 80 минут). 

sort -k 2 dna_sequences | sed -nE '{N; /^[^ ]+ ([^ ]+)\n[^ ]+ \1/p; D}'

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

...