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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Автореферат

диссертации на соискание учёной степени

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

05.13.17 - теоретические основы информатики

кандидата физико-математических наук

Торшин Иван Юрьевич

Москва 2011

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. А.А. Дородницына РАН

Научный руководитель: доктор физико-математических наук, чл.-корр. РАН Константин Владимирович Рудаков

Официальные оппоненты: доктор физико-математических наук Сметанин Юрий Геннадиевич

доктор физико-математических наук Устинин Михаил Николаевич

Ведущая организация: Московский Государственный Университет им. М.В. Ломоносова

Защита диссертации состоится 22 декабря 2011 г. в 13⁰⁰ на заседании диссертационного совета Д 002.017.02 в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан ___ ноября 2011 г.

Учёный секретарь диссертационного совета

Д 002.017.02, д.ф.-м.н., профессор В. В. Рязанов

интеллектуальный формализм распознавание алгебраический

Общая характеристика работы

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

Актуальность темы обусловлена двумя причинами. С одной стороны, критерии разрешимости и регулярности составляют существенную часть теоретических результатов алгебраического подхода к проблеме синтеза корректных алгоритмов, развиваемого научной школой академика РАН Ю.И. Журавлёва и чл.-корр. РАН К.В. Рудакова. С другой стороны, эти, допускающие конструктивную проверку критерии, до сих пор систематически не использовались для анализа реальных данных. Таким образом, проблема создания методов, позволяющих проводить формально точный анализ данных на базе алгебраических критериев разрешимости и регулярности, является актуальным теоретическим вопросом.

Актуальность темы с позиции биоинформатики обусловлена накоплением огромных массивов разрозненных данных по структуре и функции биомакромолекул (белки, ДНК, РНК) на фоне отсутствия математически обоснованных методов для установления закономерностей в разноуровневых описаниях исследуемых молекулярных систем. В частности, задачи распознавания вторичной и третичной структуры белка на основе его «первичной структуры» (аминокислотной последовательности) являются одними из важнейших задач биоинформатики и теоретической биологии белка.

Целями диссертационной работы являются (1) создание методов для формально точного интеллектуального анализа данных на основе алгебраических критериев разрешимости и регулярности и (2) разработка формализма для описания задачи распознавания вторичной структуры белка в терминах современной теории распознавания. Особое внимание уделяется развитию формализма для тестирования гипотезы о локальном характере зависимости вторичной структуры белка от его первичной структуры.

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

Методы исследования: теоретические методы, основанные на конструкциях алгебраического подхода к проблеме синтеза корректных алгоритмов; экспериментальные методы, использующие общедоступные выборки данных по третичной (PDB, Protein Data Bank, www.rcsb.org) и первичной (UNIPROT, www.expasy.org) структуре белка. Вычислительные эксперименты проводились с использованием специально разработанного комплекса программ.

Областью исследования в настоящей работе является разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных (что соответствует п. 5. паспорта специальности 05.13.17 «Теоретические основы информатики»);

Результаты, выносимые на защиту:

1. Критерии разрешимости и регулярности исследуемой задачи

2. Аппарат для формального описания гипотезы о локальности; локальные формы критериев разрешимости и регулярности на множествах объектов и мотивов.

3. Эвристические оценки информативности аминокислотных мотивов. Предложен формализм для комбинаторного тестирования условия разрешимости с учетом информативности мотивов.

4. Методика вычисления тупиковых множеств мотивов по критериям локальной разрешимости и локальной регулярности и её теоретическое обоснование.

5. Метод формирования непротиворечивых множеств объектов на основе оценок информативности.

6. Формализм для исследования морфологии вторичной структуры на основе принципа максимального покрытия ведущих позиций.

7. Тупиковые множества мотивов по критериям разрешимости и регулярности и оптимальные словари для описания вторичной структуры белка установленные при экспериментальном тестировании разработанного формализма

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

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

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

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

Материалы диссертационной работы легли в основу спецкурса «Биоинформатика и задачи распознавания в современной биологии», читаемого студентам 6-го курса на кафедре «Интеллектуальные системы» ФУПМ МФТИ.

Публикации по теме диссертации в изданиях списка ВАК: [2, 3, 4, 5, 6]. Другие публикации по теме диссертации: [1, 7, 8, 9]. Некоторые результаты работы включены в отчёты по проектам РФФИ 09-07-12098, 09-07-00212-а и 09-07-00211_а, по контракту Минобрнауки РФ № 07.514.11.4001 и по программе президиума РАН «Фундаментальные науки медицине» (2009-2011).

Апробация работы. Результаты работы докладывались, в частности, на конференциях:

Всероссийская конференция «Математические методы распознавания образов», ММРО-14, 2009 г. [7];

Международная конференция «Интеллектуализация обработки информации», ИОИ-8, 2010 г. [8];

Всероссийская конференция «Математические методы распознавания образов», ММРО-15, 201 г. [9].

Структура и объём работы. Работа состоит из оглавления, введения, пяти глав, заключения и списка литературы (39 пунктов). Общий объём работы составляет 100 стр.

Благодарность. Автор выражает глубокую признательность своему учителю чл.-корр. РАН Константину Владимировичу Рудакову за неоценимую помощь на всех этапах работы, академику РАН Юрию Ивановичу Журавлеву за внимание и поддержку, сотрудникам отдела «Интеллектуальные системы» Вычислительного Центра им. А.А. Дородницына РАН и коллегам из других организаций за конструктивную критику, советы и помощь.

Краткое содержание работы

Замечание. В автореферате сохранена нумерация основных утверждений (аксиом, определений, теорем и их следствий, формул), принятая в тексте работы.

В разделе «0. Введение. О задачах распознавания в биоинформатике» представлено краткое введение в проблемную область. В современной биологии белок рассматривается с нескольких точек зрения: (1) как одномерная последовательность аминокислот (т. н. «первичная структура белка», 1D^б); (2) как одномерная последовательность характерных локальных конфигураций («вторичная структура», 2D^б); (3) как трехмерный объект («атомная структура», «третичная структура», «четвертичная структура», «пространственная структура», представимая как набор декартовых координат атомов белка, 3D^б) и (4) как особый механизм, выполняющий определенную роль или т.н. «функцию» белка в жизнедеятельности клетки (Ф^б) [1].

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

Для решения этой задачи целесообразно решить важную промежуточную задачу - установить взаимосвязь между первичным и вторичным уровнями структуры белка или решить задачу «распознавания вторичной структуры белка». В настоящей работе данная задача рассматривается как перевод последовательности символов из одного алфавита в другой. Актуальность задачи обусловлена значительным объемом данных по первичным структурам белков и на два-три порядка меньшим количеством экспериментальных данных о пространственной структуре.

Впервые комплекс задач о взаимосвязи различных аспектов структуры белка возник в середине 1960х годов, когда были определены пространственные (3D) структуры некоторых белков. Первоначальные попытки связать аминокислотную последовательность и структуру белка на основе физико-химических принципов не были до конца успешны - средняя аккуратность такого рода методов не превышала 65%. Примечание. В качестве «аккуратности» в задаче распознавания вторичной структуры белка используется доля совпадений литер вторичной структуры (обозначается как «Q3_total»).

Некоторое увеличение аккуратности распознавания Q3_total произошло, когда для решения данной задачи стали использоваться такие методы машинного обучения как нейронные сети и машины опорных векторов. Несмотря на увеличение средней аккуратности Q3_total до 75%-80%, эти значения Q3_total являются, по всей видимости, потолком для данной группы методов. Эксперименты в рамках конференций-соревнований CASP (Critical Assesment of Protein Structure Prediction), проводимые с начала 1990-х годов, убедительно показали отсутствие значительной положительной динамики в аккуратности распознавания вторичной структуры по меньшей мере в течение 10 лет (с 1992 по 2002 годы).

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

Глава 1. Разрешимость, регулярность и локальность задачи распознавания вторичной структуры белка

В разделе «1.1. Исходные определения» определены множество начальных и финальных информаций, понятие прецедента и получены критерии разрешимости, регулярности и корректности исследуемой задачи.

Пусть заданы два алфавита: алфавит A для описания первичной структуры белка («верхнего слова») и алфавит B для описания вторичной структуры («нижнего слова»). Пусть A = {а₁, а₂, ..., а_n(A)}, n(A)=|A| > 0 и B = {b₁, b₂, …, b_n(B)}, n(B)=|B| > 0. Произвольное слово в алфавите А обозначим V=v₁v₂… v_n(V), в алфавите В - W=w₁w₂… w_n(W), n(V) и n(W) - длины слов. Пусть ? - неопределенность. Введем ?-расширенные алфавиты Г=A{?} и BЮ=B{?} и ?-расширенные множества слов и , соответственно.

Пусть задано конечное множество прецедентов , , где «Ч» обозначает декартово произведение. Прецедент, таким образом, представляет собой пару слов . Назовем V «верхним словом», а W - «нижним словом» прецедента. Решение исследуемой задачи распознавания сводится к поиску некоторой функции F: , причем (-длина слова V). Будем называть функцию F корректной, если .

Теорема 1.1: F существует тогда и только тогда, когда

(1.1).

В соответствии с теоремой 1.1, существование корректной функции (т.е. разрешимость исследуемой задачи) зависит от выбора множества Pr. Исследуемую задачу , определяемую множеством прецедентов Pr, будем называть разрешимой, если для нее существует корректная функция F. Все непустые подразделяются на те, на которых задача разрешима и на те, на которых задача неразрешима. В дальнейшем рассматриваются только непротиворечивые множества прецедентов.

Наряду с разрешимостью в современной теории распознавания обычно изучается также регулярность задач. Под регулярностью задачи понимается разрешимость самой задачи, сопровождающаяся разрешимостью задач из некоторой её окрестности в изучаемом множестве задач, так что понятие регулярности определяется тем, как задаются окрестности задачи. Следуя идеологии научной школы академика Ю.И. Журавлева, определим окрестность задачи Z с множеством прецедентов как множество задач Z' со множеством прецедентов при произвольных . Отсюда следует, что задача Z будет регулярной на множестве прецедентов Pr тогда и только тогда, когда выполняется следующее условие регулярности:

(1.2) .

1.2. Локальность

Локальность соответствует тому, что каждая литера нижнего слова определяется некоторым подсловом верхнего слова. Пусть дано слово длины n. Это может быть верхнее слово (V) или нижнее слово (W). Определим ведущую позицию i, 1? i ? n. Дана также «маска» , где м_i , м₁< м₂< …<м_m. Будем называть м_i позициями. Параметр m назовем размерностью маски и будем обозначать как , а параметр м_m - м₁ + 1 назовем протяженностью маски и обозначим как . Определим оператор выбора подслова :

(1.3)

Пусть имеется система масок M =. Будем считать, что

, …, .

Определим одноэлементную систему масок как объединенную маску такую, что .

Слова в множестве прецедентов Pr имеют конечную длину, поэтому вводится понятие (L,R)-корректности функции F: выполнено , где , и при , L, R N {0}. При заданной системе масок M можно предложить два принципиально различных способа определения границ для описания краевых эффектов: (1) как значений L(M) и R(M) при которых применимы все маски из и (2) как значений l(M) и r(M) при которых применима по крайней мере одна маска из M.

Теорема 1.2. (l(M), r(M))-корректная функция также (L(M), R(M))-корректна. l(M),r(M)-корректность гарантирует корректность распознавания на концах верхнего слова, а L(M),R(M)-корректность необходима для выбора безизбыточных систем масок.

В разделе «1.3. Условие существования локальных функций» гипотеза о локальности исследуемой задачи распознавания формулируется как гипотеза о существовании некоторой корректной локальной функции такой, что для всякого и , , а при выполнено .

Таким образом, условие разрешимости задачи распознавания вторичной структуры белка может быть сформулировано следующим образом (критерий локальной разрешимости):

(1.6)

,

Теорема 1.3. Локальная функция , корректная на множестве прецедентов , существует тогда и только тогда, когда выполняется критерий локальной разрешимости.

Следствие 1. Из теорем 1.2 и 1.3 следует критерий локальной (L(M), R(M))-разрешимости

Введем критерий локальной разрешимости с использованием отдельных масок:

(1.6”) ,

, ,

Теорема 1.4. Условия (1.6) и (1.6”) эквивалентны.

Критерием, определяющим наличие у задачи свойства локальной регулярности будем называть следующее условие:

(1.7),

, ,

В разделе «1.4. Разрешимость задачи и монотонность условия разрешимости» рассматривается монотонность условия разрешимости (1.6) по M. В разделе «1.5. 0-тупиковость и тупиковость систем масок» монотонность условия разрешимости рассмотрена с точки зрения тупиковых систем масок.

Если условие (1.6) выполнено для M, но не выполнено для любой такой, что , то систему масок назовём 0-тупиковой. Тупиковой назовём такую систему масок, что условие (1.6) нарушается для любой .

По аналогии с задачей упрощения д.н.ф. маску , будем называть ядерной, если . «Ядерными» системами или подсистемами масок будем называть M, обладающие свойством ядерности:

(1.8)

Теорема 1.5. M - тупиковая система масок тогда и только тогда, когда М обладает свойством ядерности.

Следствие 1. Из тупиковости следует 0-тупиковость.

Следствие 2. Если в некоторой 0-тупиковой системе масок M имеется ядерная маска , то входит во все тупиковые подсистемы M.

Следствие 3. Пусть в 0-тупиковой M есть несколько ядерных масок (ядерная подсистема). Если некоторая , то не входит ни в одну тупиковую M.

Теорема 1.5 и её следствия полезны для разработки алгоритмов построения тупиковых M.

Глава 2. Анализ информативности мотивов на основе критерия локальной разрешимости

Критерий локальной разрешимости (1.6, 1.6") соответствует локальной форме задачи распознавания вторичной структуры. Элементарными объектами q (в дальнейшем, просто «объектами») назовем элементы множества . Элементами наблюдаемых множеств объектов Q(Pr,M)={q₁,q₂,…,q_N}, N=|Q(Pr,M)| являются пары ; каждая пара есть совокупность подслова, выбранного по в i-ой ведущей позиции верхнего слова () и i-ой литеры нижнего слова () j-го прецедента.

Назовем мотивами элементы множества . Мотив присутствует в объекте , если . Обозначим принадлежность мотива объекту q как . Для произвольной пары объектов и мотив назовем отличающим, если присутствует в одном из объектов и отсутствует во втором.

Теорема 2.1. Условие локальной разрешимости задачи выполнено тогда и только тогда, когда для каждой пары объектов и при существует хотя бы один отличающий мотив. Теорема 2.1 позволяет записать условие (1.6") как критерий разрешимости на множестве мотивов:

(2.3) .

Утверждение (2.3) соответствует переходу от задачи Z(Pr, M) к эквивалентной задаче Z(Q, К), в которой в качестве параметров выступают множество объектов Q=Q(Pr, M) и множество мотивов К= К(Pr, M).

В разделе «2.2. Монотонность условия разрешимости и тупиковые системы мотивов» рассмотрена монотонность условия локальной разрешимости в форме (2.3) для нахождения тупиковых множеств мотивов. Изучение монотонности условия (2.3) на множествах мотивов - гораздо более «тонкий» исследовательский инструмент, так как позволяет удалять отдельные мотивы, а не блоки мотивов, как это происходит при удалении масок (раздел 1.5).

В разделе «2.3. Эвристические оценки информативности мотивов» введено несколько эвристических оценок информативности мотивов, основанных на частотах встречаемости мотивов в различных классах объектов. Оценки информативности D: К>R₊ позволяют провести редукцию множества мотивов К(Pr, M). При этом критерий разрешимости изучаемой задачи распознавания (2.3) служит условием, предотвращающим удаление отличающих мотивов, обеспечивающих разрешимость задачи.

Пусть каждый мотив к_б К(Pr, M) входит в состав объектов из Q; - частота встречаемости значения . Тогда , оценку информативности б-го мотива по литере , можно определить как:

(2.4)

На информативность мотива также влияет частота его встречаемости среди объектов, поэтому вводятся такие оценки информативности б-го мотива как , и др.

2.4. Информативность мотивов и условие разрешимости

Вводимое D отношение порядка на R₊ порождает линейный порядок на множестве мотивов . Принцип отбора мотивов в упорядоченном множестве I() состоит в том, что для каждой пары объектов из Q находится различающий мотив с наивысшей информативностью.

Теорема 2.2. Множество K₁ является тупиковым тогда и только тогда, когда для каждого мотива из множества K₁ во множестве Q существует хотя бы одна пара объектов, для которой данный мотив - единственный различающий.

В ходе доказательства теоремы 2.2 вводится функция К_f (i, j), находит единственный мотив с максимальным D, который позволит различить i-ый и j-ый объекты из Q:

(2.5)

Минимальное множество мотивов K₁, на котором сохраняется разрешимость, K₁, определяется следующим образом через характеристическую функцию T(б):

(2.6)

После вычисления T(б) для всех пар объектов из Q, каждому i-му объекту из Q соответствует различающих мотивов из K₁, . Объекты с =0 назовем «нуль-объектами», а с =1 - «1-объектами».

Следствие 1. В общем случае множество не является тупиковым.

Следствие 2. Тупиковое множество мотивов может быть найдено путём итеративного удаления из мотивов с наименьшей информативностью.

Следствие 3. Наличие всех нуль-объектов в одном классе - необходимое условие разрешимости задачи.

Следствие 4. Наличие всех нуль-объектов в одном классе - необходимое условие тупиковости .

Следствие 5. Тупиковость гарантирована только при постановке задачи в двухклассовой форме.

Теорема 2.2 и ее следствия позволяют вычислить минимальное и тупиковое множества мотивов максимальной информативности.

В разделе «2.5. Об оценках информативности и непротиворечивых множествах объектов» показано, что помимо нахождения тупиковых множеств мотивов эвристические оценки информативности мотивов могут также использоваться для решения важной промежуточной задачи - формирования непротиворечивых множеств объектов.

Глава 3. Об использовании критериев локальной разрешимости и регулярности для исследования морфологии первичной структуры

Условие локальной разрешимости задачи на множествах мотивов (выражение 2.3) выполнено тогда и только тогда, когда для каждой пары объектов и при во множестве мотивов К существует хотя бы один отличающий мотив (теорема 2.1). Введем численную оценку разрешимости задачи Z(Q, K). Пусть r₁= N_(2.3)/N•(N-1), где N=|Q|, а N_(2.3) - множество пар объектов в Q, на котором выполнено условие (2.3) при использовании множества мотивов K. Очевидно, что в разрешимой задаче Z(Q, К) всегда выполнено r₁=1.

Теорема 3.1. Условие локальной регулярности выполнено тогда и только тогда, когда при заданном K для каждой пары объектов из Q существует хотя бы один отличающий мотив. Утверждение теоремы эквивалентно условию регулярности на множестве мотивов:

(3.2) .

Если задача Z(Q, К) - регулярна, то будем называть Q регулярным множеством объектов, а К - регулярным множеством мотивов. Пусть r₀= N_(3.2)/N•(N-1), где N=|Q|, а N_(3.2) - множество пар объектов, на котором выполнено условие (3.2). В регулярной задаче Z(Q, К) выполнено r₀=1. Регулярное множество мотивов назовём тупиковым, если условие (3.2) выполнено для К, но не выполнено для любого К' К.

Теорема 3.2. В задаче Z(Q, К) тупиковое множество мотивов К₁, обеспечивающее разрешимость, является подмножеством тупикового множества мотивов К₀, обеспечивающего регулярность.

Следствие 1. Пусть - параметр, описывающий соответствие множества К₁ множеству К₀. В условиях теоремы =0.

Следствие 2. Пусть . В условиях теоремы =1.

Для редукции наблюдаемого множества мотивов К(Q, M) также могут быть использованы введённые в главе 2 эвристические оценки информативности мотивов. В случае тестирования условия регулярности (3.2), оценка информативности мотива может быть определена просто как частота встречаемости .

Теорема 3.3. При заданной оценки информативности мотивов множество К₀, обеспечивающее выполнение условия регулярности на множестве объектов Q, является тупиковым тогда и только тогда, когда для каждого мотива из К₀ в Q существует хотя бы одна пара объектов для которой данный мотив - единственный различающий.

При экспериментальном тестировании регулярности и разрешимости целесообразно проводить усреднение вычисляемых К₁ и К₀ по различным выборкам объектов одного размера. Для усреднения множеств мотивов вводится - заполненность элементарного мотива при тестировании n выборок объектов, .

Размер выборки объектов |Q| является важным параметром, определяющим значения заполненности конкретных мотивов при данной системе масок. Величины |Q| и |К(Q,M)| определяют мощности множеств мотивов К₁ и К₀ так, что выполнена

Теорема 3.4. При фиксированном К=К(Q,M), |K₀|=f(|К|,|Q|), причём f - монотонна по |Q|.

Следствие 1. r₀ монотонно возрастает с увеличением |Q|

Следствие 2. Справедливо соответствующее утверждение для разрешимости.

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

Глава 4. Построение оптимальных В-алфавитов как инструмент исследования морфологии вторичной структуры

В разделе «4.1. Об алфавитах для описания вторичной структуры белка» рассмотрены особенности начальных данных по вторичной структуре белка. Алфавит В может быть определён существенно разными способами: (1) базовые алфавиты, (2) производные алфавиты на основе последовательностей литер базового алфавита, (3) расширение базового алфавита с учетом сегментов вторичной структуры нижнего слова.

Базовый алфавит типа В можно определить как трехбуквенный, m=|B|=3, В={H, S, L}, где “H” (от англ. helix) обозначает конфигурацию типа «спираль»; “S” (strand) обозначает конфигурацию «стрэнд» (плоский вытянутый участок белковой цепи) и “L” (loop) - участок произвольной структуры, т.е. не-H и не-S. Этот трехбуквенный алфавит отображает принципиально различные трехмерные пространственные конфигурации, которые может принимать тот или иной учаcток белковой цепи.

Возможно определение производного алфавита В через пары букв базового В-алфавита. Экспертный анализ частот встречаемости этих пар букв позволил сделать несколько важных выводов о сегментной структуре нижних слов.

Возможно расширение базового алфавита с учетом сегментной структуры нижних слов. С физической точки зрения, такой расширенный алфавит позволяет подчеркнуть различия в пространственных конфигурациях индивидуальных аминокислотных остатков вдоль белковой цепи. Например, литера расширенного алфавита соответствует последней (англ. «end») литере сегмента петли …LLL, который переходит в спиральный HHH… сегмент.

В разделе «4.2. Сложность В-алфавита и критерий локальной разрешимости» рассматривается вопрос о том, насколько целесообразно усложнять описание В-алфавита с точки зрения сформулированного ранее критерия локальной разрешимости.

Алфавит B^р есть расширение базового алфавита B^б, если существует такая функция f_B : B^р B^б, что ею определяется однозначный перевод всех литер алфавита B^р в соответствующие литеры алфавита B^б.

Теорема 4.1. Расширение B-алфавита может приводить к потере локальной разрешимости задачи Z(Pr, M).

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

4.3. Принцип максимального покрытия ведущих позиций

Пусть имеется множество прецедентов Pr. Для упрощения изложения формализма проведём конкатенацию верхних и нижних слов прецедентов так, что образуется одноэлементное множество прецедентов Pr', содержащее прецедент P=(V,W), где W - нижнее слово прецедента P и |P| = |V| = |W| = N, N>0.

Пусть имеется базовый алфавит B={b₁, b₂, …, b_n(B)}. Обозначим множество слов длины n как Bⁿ, тогда множество содержит все слова в, образованные над алфавитом B. Длину символьной последовательности слова в обозначим . Однородным сегментом будем называть слово, являющееся повтором единственной литеры алфавита B. Однородному сегменту в соответствует образующая литера b(в). Набор слов, комбинацией которых можно получить нижнее слово W, будем называть B-словарём или словарём B, B, B где - множество всех В-словарей.

Лемма 4.2. Существуют В-словари, состоящие только из однородных слов.

Оптимальным В-словарём будем называть словарь B^* =, содержащий минимальное число элементов (слов) в алфавите B при максимальной длине каждого элемента:

(4.1)

Слово покрывает позицию i в W по маске если . Определим оператор покрытия ведущих позиций I^*(P,), который для элемента произвольного B=, B формирует подмножество ведущих позиций в P такое, что I^*(P, ) = , где - произвольная маска, удовлетворяющая условию =.

Лемма 4.3. Для однородных мощность множества покрытых позиций монотонно убывает с возрастанием .

Назовём частичным или о-покрытием нижнего слова W такое множество для которого выполнено условие частичного покрытия:

(4.2)==, о ? 1.

Для заданных W и выражение (4.2) позволяет оценить значение о, так что о= о(, W ). Покрытием нижнего слова W назовём множество B для которого о(, W )=1. В соответствии с определением В-словаря, любое покрытие B является словарём, т.е. B.

Лемма 4.4. - необходимое условие покрытия.

Следствие 1. Утверждение леммы справедливо для частичного покрытия.

Следствие 2. Любое В для которогоне является покрытием.

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

(4.3)

Теорема 4.5. Условие максимального покрытия ведущих позиций - необходимое условие оптимальности словаря.

В ходе доказательства теоремы вводится понятие д(о)-покрытия I_j,д() = {в_j, в_j+1,…,в_j+д-1}:

(4.4) ?.

Следствие 1. При фиксированном j, мощность словаря I_j,д() монотонно возрастает с увеличением о.

о-тупиковым покрытием B^Т будем называть такое о-покрытие, при котором (4.3) выполняется для B^Т и не выполняется для любого В'B^Т.

Теорема 4.6. д(о)-покрытия содержат о-тупиковые покрытия.

о,г-разбиением нижнего слова W назовём о-покрытие для которого выполнено условие г-разбиения:

(4.5)

Теорема 4.7. о,г-разбиение является тупиковым покрытием.

Следствие. о,г-разбиения - подмножества д(о)-покрытий. Принципом максимального покрытия назовём утверждение о максимальном вкладе б-го элемента о,г-разбиения I_j,д(j)() в покрытие нижнего слова W :

(4.6)

Теорема 4.8. Оптимальный словарь B^* является о,г-разбиением, B^* Г(о), построенным на основе принципа максимального покрытия.

Построенный на основании предлагаемого формализма алгоритм нахождения оптимальных словарей выглядит следующим образом. Для заданных n (10..40), о (0.9..1.0) и г (0..0.1) строится список I() и в этом списке выделяются д(о)-покрытия, формирующие список I(Д(о)). На основание списка д(о)-покрытий строятся о,г-разбиения I(Г(о)), из которых по условию (4.1) выбираются оптимальные.

Глава 5. Экспериментальное тестирование разрабатываемого формализма

В разделе «5.1. Формирование непротиворечивых множеств объектов» описано формирование непротиворечивого множества объектов в соответствии с методикой, предложенной в разделе 2.5. В проведенных экспериментах, в качестве множества прецедентов были использованы все 165,000 прецедентов, представленные в базе данных PDB на октябрь 2011. Исследовались выборки из 10000, 20000, 30000, 50000, 100000, 200000 объектов, сформированные путем случайного отбора объектов без возвращения. Локальная регулярность задачи также тестировалась на множествах объектов, полученных на основе всех известных аминокислотных последовательностей в базе данных UNIPROT, в которой присутствует 15 млн. попарно различных последовательностей общей длиной в 5•10⁹ литер (данные на август 2011).

В разделе «5.2. Комбинаторное тестирование критерия локальной разрешимости» представлены результаты экспериментального тестирования условия локальной разрешимости на множествах мотивов (глава 2). Вычисления T(б) показали, что предложенный формализм позволяет значительно сократить множество мотивов K(Pr, M) с получением тупиковых К₁ без потери разрешимости. Например, в К(Pr(|Q|=200000), ) содержалось 201000 мотивов. Число отобранных мотивов (т.е. |К₁|=|{T(б)=1}|) составило ~25000. Логарифмический характер зависимости числа отобранных мотивов от |Q| позволяет предположить, что высокая эффективность редукции множества мотивов сохранится и при значительно бомльших Q.

Результаты анализа указывают на существование некоторого «ядра» в тупиковых множествах мотивов. Мотивы, входящие в такое «ядро», обеспечивают разрешимость на большинстве пар объектов. Полная разрешимость достигается добавлением к «ядру» некоторых низкоинформативных мотивов, каждый из которых обеспечивает разрешимость всего лишь на нескольких парах объектов.

Исследование заполненности мотивов z_б во множествах К₁, полученных для разных Q одного размера показало, что чем выше информативность мотива (т.е. чем ниже б), тем более вероятно, что мотив входит в тупиковое К₁, построенное на произвольном Q. Мотивы с заполненностью 1.0 (т.е. встречающиеся в К₁, построенном на произвольном Q) обеспечивают разрешимость 90% пар объектов.

В разделе «5.3. Комбинаторное тестирование критерия локальной регулярности» представлены результаты экспериментов по вычислению тупиковых множеств мотивов, обеспечивающих регулярность задачи Z(Q, К). Тестирование разрешимости и регулярности показало, что наилучший результат (в соответствии со значениями параметра оценки разрешимости r₁, Глава 3) показала система масок (r₁=0.94±0.01; |Q|=2•10⁵). Для данной системы масок r₁?0.99 достигалось при минимальной заполненности мотивов =0.7.

Результаты тестирования выполнимости условия регулярности на выборках из PDB и UNIPROT с использованием показало, что параметр имел наименьшее значение (=0.005±0.003) в системах масок и . При этом, множества вида {к_б(К₁К₀)|z_б=1} обеспечивали различение 0.9995 пар объектов по критерию регулярности (3.2). В системе масок значение r₀ достигало 0.99 при |Q|=7•10⁵_, в то время как показало более медленный рост (r₀=0.99 при |Q|=1.2•10⁶). Замедленный рост связан с тем, что мотивы, содержащиеся в структурах кристаллизованных белков, встречаются намного реже в произвольной выборке аминокислотных последовательностей.

Тупиковые множества мотивов, получаемые в результате тестирования критерия (3.2), характеризуют морфологию или, в некотором смысле, «структуру» аминокислотных последовательностей. Более чем для 90% объектов, мотивы К₀ покрывают не все позиции объекта, выделяя тем самым некоторые «информативные» позиции аминокислотной последовательности, соответствующие «информативным» мотивам.

В разделе «5.4. Построение оптимальных В-словарей» представлены результаты экспериментов по определению словарей из элементов фиксированной длины и словарей элементов различных длин. При построении В-словарей как о,г-разбиений (теорема 4.8) использовались значения n10, о=0.95 и г=0. На основании расчётов для з выборок вычислялась заполненность z(B) каждого из полученных словарей B (если словарь В был найден в з₂ из з исследованных множеств вторичных структур, то его заполненность z(B)= з₂/з). Несмотря на то, что было найдено более 50 оптимальных словарей, эксперименты позволили установить всего 7 словарей с заполненностью 1.0. Наибольший интерес представляет оптимальный словарь {HHHHH, LLLLL, SSSSS, LLSSS}.

В качестве иллюстрации перспектив практического применения разрабатываемого формализма, в разделе «5.5. Эмпирическая схема распознавания вторичной структуры» предложена эмпирическая схема распознавания вторичной структуры белка и приводятся результаты тестирования полученной эвристики на множествах непротиворечивых прецедентов. Использованная схема распознавания вторичной структуры была основана на принципе голосования. Несмотря на очевидную примитивность предлагаемой схемы распознавания, в кросс-валидации была достигнута аккуратность распознавания Q3_total=0.84±0.02 при одинаковых весах мотивов. Использование весов мотивов (нормализованные значения ) и оптимального В-словаря {HHHHH, LLLLL, SSSSS, LLSSS} приводило к повышению аккуратности распознавания (Q3_total =0.89±0.025). Наиболее значимым недостатком данной схемы распознавания является заметное количество отказов от распознавания (т.е. ответ «Д», неопределённость) для 15..20% позиций произвольной первичной структуры.

Публикации по теме диссертации

1. Torshin I.Y. Bioinformatics in the Post-Genomic Era: The Role of Biophysics, 2006. Nova Biomedical Books, NY, ISBN: 1-60021-048

2. Рудаков К.В., Торшин И.Ю. Вопросы разрешимости задачи распознавания вторичной структуры белка. Информатика и её применения, Т.4., № 2, 2010, с. 25-35.

3. Рудаков К.В., Торшин И.Ю. Анализ информативности мотивов на основе критерия разрешимости в задаче распознавания вторичной структуры белка. Информатика и её применения, Т. 5, № 4, 2011, с. 40-50.

4. Журавлёв Ю.И., Рудаков К.В., Торшин И.Ю. Алгебраические критерии локальной разрешимости и регулярности как инструмент исследования морфологии аминокислотных последовательностей. Труды МФТИ. - 2011 - Т.3. № 4, с.67-76.

5. Рудаков К.В., Торшин И.Ю. Об отборе информативных значений признаков на базе критериев разрешимости в задаче распознавания вторичной структуры белка. ДАН, 2011, Т. 441, № 1, с.1-5.

6. Torshin I. Yu. On solvability, regularity, and locality of the problem of genome annotation. Pattern Recognition and Image Analysis, 2010, V. 20(3): 386-395.

7. Рудаков К.В., Торшин И.Ю. О разрешимости формальной задачи распознавания вторичной структуры белка. ММРО-14, Суздаль, 21-25 сентября, 2009, С. 596-597.

8. Торшин И.Ю. Анализ мотивов в задаче распознавания вторичной структуры белка на основе критерия разрешимости. Международная конференция «Интеллектуализация обработки информации» (ИОИ-8), Кипр, г. Пафос, 17-23 октября 2010 г, с.487-490.

9. Торшин И.Ю. Критерии локальной разрешимости и регулярности в анализе данных аминокислотных последовательностей. ММРО-15, Петрозаводск, 11-17 сентября, 2011, С. 590-594.

Размещено на Allbest.ru

...