Выравнивание последовательности ДНК в нативном Python (без биопиона) - PullRequest
Новая
       49

Выравнивание последовательности ДНК в нативном Python (без биопиона)

1 голос
/ 10 марта 2010

У меня есть интересная генетическая проблема, которую я хотел бы решить на нативном Python (ничего кроме стандартной библиотеки). Это для того, чтобы решение было очень простым в использовании на любом компьютере, не требуя от пользователя установки дополнительных модулей.

Вот оно. Я получил 100 000 последовательностей ДНК (до 2 миллиардов) из 454 серий нового поколения. Я хочу обрезать конечности, чтобы удалить праймеры, которые могут присутствовать на обоих концах, как в обычном, так и в смысловом порядке. Пример: 

seq001: ACTGACGGATAGCTGACCTGATGATGGGTTGACCAGTGATC
        --primer-1---                 --primer-2-

Праймеры могут присутствовать один или несколько раз (один сразу за другим). Нормальный смысл всегда слева, и обратный справа. Моя цель, таким образом, найти праймеры, вырезать последовательность так, чтобы осталась только часть, не содержащая праймеров. Для этого я хочу использовать классический алгоритм выравнивания (например, Смит-Уотерман), который был реализован на нативном Python (то есть: не с помощью биопиона). Мне известно о том, что для этого может потребоваться некоторое время (до нескольких часов).

Примечание: это НЕ прямой поиск по слову, поскольку ДНК, как в последовательностях, так и в праймерах, может быть "мутирована" по разным техническим причинам.

Что бы вы использовали?

Ответы [ 3 ]

1 голос
/ 11 марта 2010

Кратко исследуя этот алгоритм, это не простая вещь. Это займет очень серьезную работу с алгоритмом. Попробуйте перевести ваши ожидания с «часов» в «дни или недели».

Программисту, реализующему это, потребуется:

  • Высокая компетентность в общем программировании на Python
  • Опыт программирования на алгоритмах и хорошее понимание сложности времени.
  • Хорошее понимание структур данных Python, таких как dict, set и deque, и их характеристик сложности.
  • Знакомство с юнит-тестами.

Этот программист может быть или не быть вами прямо сейчас. Это звучит как отличный проект, удачи!

1 голос
/ 10 сентября 2010

Вы могли бы сделать это довольно просто с помощью регулярных выражений? Я не думаю, что это будет так сложно! На самом деле, я только что закончил некоторый код, чтобы сделать что-то похожее на это для одного из парней в университете!

Если не искать точных копий праймеров, из-за мутации может быть применен элемент нечеткого соответствия! Версия, которую я сделал, очень просто искала точные совпадения праймеров в начале и конце и возвращала значение минус те праймеры, используя следующий код: 

pattern = "^" + start_primer + "([A-Z]+)" + end_primer + "$" # start primer and end primer are sequences you are looking to match
regex = re.match(pattern, sequence) # sequence is the DNA sequence you are analyzing
print regex.group(1) # prints the sequence between the start and end primers

Вот ссылка на нечеткое регулярное выражение в python http://hackerboss.com/approximate-regex-matching-in-python/

1 голос
/ 10 марта 2010

Вот статья примерно на эту тему:

Rocke, Об обнаружении новых зазубренных мотивов в последовательностях ДНК, 1998 .

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

...