Реклама на сайте (разместить):



Реклама и пожертвования позволяют нам быть независимыми!

Сравнение символьных последовательностей

Материал из Викизнание
Перейти к: навигация, поиск
Эвентология
Открытый Helgus~µастер~Kласс — H~µ~K
Это незавершённая статья из области эвентологии и её применений, редактируемая при участии Мастера

СРАВНЕНИЯ СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ[править]

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

Метод выравнивания[править]

Наиболее распространённым способом сравнения символьных последовательностей является выравнивание (alignment). Суть этого метода заключается в том, чтобы «подогнать» одну последовательность под другую. Точнее, пусть одна последовательность (называемая опорной); пусть имеется другая последовательность, которую необходимо выровнять относительно первой. С этой второй последовательностью разрешается делать следующие преобразования: можно вставить пробел (пустой символ, отсутствующий в исходном алфавите), можно удалить символ, можно заменить один символ на другой. Каждой такой операции (их ещё называют редакционными преобразованиями) приписывается определенный штраф (значение весовой функции). Среди всех мыслимых укладок (выравниваний), которые можно получить с помощью указанных выше операций, наилучшей считается та, которая обеспечивает минимум суммы штрафных функций. Метод выравнивания является типичной задачей динамического программирования и обладает рядом недостатков: во-первых, выравнивание может быть неединственным, во-вторых, не существует «естественного» способа назначения штрафных функций (и их выбор может оказать существенное влияние на результат), в-третьих, метод является несимметричным — результат выравнивания будет зависеть от выбора опорной последовательности. Несмотря на все недостатки, метод выравнивания получил широкое распространение.

Метод сравнения по частотным словарям[править]

В настоящей работе рассмотрен другой метод сравнения символьных последовательностей, основанный на сравнении их частотных словарей. Данный метод свободен от всех недостатков, указанных выше. Целью настоящей работы является сравнение двух методов сравнения символьных последовательностей — выравнивания и сравнения с помощью частотных словарей. Опишем кратко метод сравнения с помощью частотных словарей. Пусть имеется последовательностей из одного и того же алфавита (длина из несущественна). Составим для каждой последовательности серию частотных словарей W_{{1}}^{{(j)}}, W_{{2}}^{{(j)}}, …,W_{{q}}^{{(j)}} возрастающей толщины; индекс {j} нумерует последовательности. Затем для каждого набора (из словарей одинаковой толщины) построим специальный промежуточный словарь, называемый гибридным. Частоты слов в W_{{q}}^{{(G)}} определяются следующим образом:



f_{{w}}^{{(G)}}={\frac  {f_{{w}}^{{(1)}}+f_{{w}}^{{(2)}}+\ldots +f_{{w}}^{{(K)}}}{K}}\quad (1)

Заметим, что такой гибридный словарь может не соответствовать никакой реальной последовательности. W_{{q}}^{{(G)}} является ядром сравниваемой группы. Мера близости в группе последовательностей определяется не относительно друг друга, а относительно гибридного словаря:


I^{{(j)}}=\sum \limits _{{w}}f_{{w}}^{{(j)}}\ln {\frac  {f_{{w}}^{{(j)}}}{f_{{w}}^{{G}}}} (2)

Величина (2) есть мера неопределённости конкретного частотного словаря в сравниваемой группе относительно из общего статистического предка. Мера (2) не является метрикой. Несмотря на простоту и краткость формулировки меры сравнения (2) при определении (1) гибридного частотного словаря, она удовлетворяет весьма важному экс-тремальному принципу:


I^{{(1)}}+I^{{(2)}}+I^{{(3)}}+\ldots +I^{{(K-1)}}+I^{{(K)}}\rightarrow \min (3)

Применение методов на практике.[править]

Целью работы было сравнение двух методов сравнения последовательностей: метод выравнивания и метода и сравнения с помощью частотных словарей. Для этого в EMBL–банке брались депонированные там группы выровненных последовательностей, послед чего по тем последовательностям, которые входили в группу, составлялись частотные словари толщиной 1<q<3, вычислялись соответствующие гибридные частотные словари и определялась мера близости от каждого из словарей в сравниваемой группе до гибридного словаря (данной группы). Приведём пример сопоставления двух методов сравнения. В EMBL–банке была взята группа выровненных последовательностей 10-ти плазмоидальных малых субъединиц рибосомальных РНК 9-ти организмов (все — грибы рода Plasmodium). Эти последовательности были выровнены и депонированы в EMBL–банке. Для каждой последовательности из группы составлялся словарь толщины q=3 . По этим словарям был построен гибридный словарь и вычислялись значения (2). В Таблице приведены результаты вычислений; последовательности расположены в том порядке, который определяется выравниванием.

Пример 1[править]

Tabl1.jpg



N — порядковый номер последовательности в случае упорядочения по значениям условной энтропии;

I — условная энтропия (2);

S — абсолютная энтропия.

Во примере №2 была взята группа из 6 последовательностей. Здесь произведено выравнивание элементов подобных элементам лосося, форели, зебрафиш и кэтфиш.

Пример 2[править]

Tabl2.jpg

Во примере №3 была взята группа из 9 последовательностей. Канал калия; канальный ген калия семейного выравнивания.

Пример 3[править]

Tabl3.jpg

Выводы и заключения[править]

Предложенный метод сравнения по частотным словарям свободен от ограничений, характерных для методов выравнивания. В частности, сравнение по частотным словарям позволяет сравнивать произвольное количество последовательностей произвольной длины, что актуально для задач современной биоинформатики. Сравнение двух методов сравнения последовательностей показывает, что эти два метода дают одинаковые (или близкие) результаты для случая сильно различающихся последовательностей. Для случая близких последовательнос¬тей результаты, как правило, различаются, причем наибольшие расхождения в группах последовательностей, выделяемых как наиболее близкие в смысле каждого из методов. --Lime 18:28, 28 <мая> 2008 (MSD)

См. также[править]

Статью можно улучшить?
✍ Редактировать 💸 Спонсировать 🔔 Подписаться 📩 Переслать 💬 Обсудить
Позвать друзей
Вам также может быть интересно: