Алгоритм Тиресиаса - Википедия - Teiresias algorithm

В Алгоритм Тиресиаса комбинаторный алгоритм для обнаружения жестких паттернов (мотивов) в биологических последовательностях. Он назван в честь греческого пророка. Teiresias и был создан в 1997 году Исидор Ригутсос и Арис Флоратос.[1]

Проблема поиска сходства последовательностей в первичной структуре родственных белков или генов возникает при анализе биологических последовательностей. Можно показать, что обнаружение закономерностей в общем виде NP-жесткий.[2] Алгоритм Тиресиаса основан на наблюдении, что если узор занимает много позиций и выглядит точно k раз во вводе, тогда должны появиться все фрагменты (подшаблоны) шаблона по меньшей мере k раз на входе. Алгоритм может создавать все шаблоны, которые имеют определенное пользователем количество копий на заданном входе, и ему удается быть очень эффективным, избегая перечисления всего пространства. Наконец, алгоритм сообщает о мотивах, максимальных как по длине, так и по композиции.

Новая реализация алгоритма Тиресиаса была недавно предоставлена Центр вычислительной медицины в Университете Томаса Джефферсона. Teiresias также доступен через интерактивный пользовательский веб-интерфейс того же центра. Смотрите внешние ссылки для обоих.

Описание шаблона

Алгоритм Тиресиаса использует обычные выражения для определения шаблонов. Это позволяет сообщаемым шаблонам состоять не только из символов, которые появляются в каждой позиции (литералы), но и из определенной группы символов (литералы в квадратных скобках) или даже из любого символа (подстановочный знак). Шаблоны, созданные алгоритмом, - это шаблоны , которые имеют не менее k экземпляров во входных данных, где L ≤ W и L, W, k натуральных чисел. Шаблон называется шаблоном тогда и только тогда, когда любые L последовательных литералов или литералов в квадратных скобках охватывают не более W позиций (т.е. может быть не более W-L подстановочных знаков).

Алгоритм сообщает только максимальные паттерны. Для данного набора последовательностей S шаблон P, который появляется k раз в S, называется максимальным тогда и только тогда, когда не существует шаблона P ', который является более конкретным, чем P, и также появляется точно k раз в S. Если существует такой образец P ', то мы говорим, что P не может быть максимальным и P считается включенным в P'. Шаблон P 'считается более конкретным, чем шаблон P, тогда и только тогда, когда P' может быть получен из P путем (а) разыменования подстановочного символа, или (b) создания экземпляра заключенного в скобки литерала к литералу, или (c) добавления строка литералов, заключенных в квадратные скобки литералов или / и подстановочных знаков справа от P, или (d) добавление строки литералов, заключенных в квадратные скобки литералов или / и подстановочных знаков слева от P.[3]

Описание алгоритма

Teiresias состоит из двух фаз: сканирования и свертки. На первом этапе входные данные сканируются на предмет шаблонов, удовлетворяющих минимальным требованиям, элементарных шаблонов. В элементарные шаблоны состоит ровно из L литералов и / или литералов в квадратных скобках и включает не более W-L подстановочных знаков. Во время свертки элементарные шаблоны рекурсивно комбинируются и создаются максимальные шаблоны. Порядок, в котором выполняются свертки, очень важен, поскольку он гарантирует, что все шаблоны будут сгенерированы, и все максимальные шаблоны будут сгенерированы раньше всех шаблонов, которые в них включены. Порядок продиктован следующими правилами

  • Приоритет каждого шаблона определяется его содержимым слева направо.
  • Литерал имеет более высокий приоритет, чем литерал в квадратных скобках, и оба имеют более высокий приоритет, чем подстановочные знаки (более конкретный первый).
  • Более длинные шаблоны имеют более высокий приоритет, чем более короткие.
  • Связи разрешаются по алфавиту.

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

Сложность времени

Алгоритм "чувствителен к выходу". Временная сложность алгоритма TEIRESIAS составляет[3]

куда L и W параметры, определяемые пользователем, которые определяют «минимальную плотность» узора (любой L литералы или скобки не могут превышать W позиции), м это количество символов, которое включает ввод, C ≤ 1 - среднее количество шаблонов, найденных в хеш-записи, тЧАС - время, необходимое для нахождения хеш-записи, соответствующей любому заданному хеш-значению, а сумма Σ - это максимальное количество шаблонов, которые когда-либо будут помещены в стек, который сохраняет шаблоны для расширения во время свертки.

внешняя ссылка

Рекомендации

  1. ^ Ригутсос, И., Флоратос, А. (1998) Открытие комбинаторных паттернов в биологических последовательностях: алгоритм TEIRESIAS. Биоинформатика 14: 55-67
  2. ^ Майер, Д., "Сложность некоторых проблем, связанных с подпоследовательностями и суперпоследовательностями", журнал ACM, 322-336, 1978
  3. ^ а б Флоратос А. и Ригутсос И., «О временной сложности алгоритма Тиресиаса», технический отчет IBM RC 21161 (94582), Исследовательский центр IBM TJ Watson, 1998 г.