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




Скачать 301.67 Kb.
НазваниеМодели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка
страница1/3
Дата публикации16.09.2014
Размер301.67 Kb.
ТипАвтореферат
shkolnie.ru > Информатика > Автореферат
  1   2   3


На правах рукописи

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

МОДЕЛИ И АЛГОРИТМЫ ОБНАРУЖЕНИЯ ЛОКАЛЬНЫХ ЗАКОНОМЕРНОСТЕЙ В ЗАДАЧЕ РАСПОЗНАВАНИЯ ВТОРИЧНОЙ СТРУКТУРЫ БЕЛКА

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

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

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

Москва 2011

Работа выполнена в Учреждении Российской академии наук

Вычислительный центр им. А.А. Дородницына РАН

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

чл.-корр. РАН

Константин Владимирович Рудаков

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

Сметанин Юрий Геннадиевич

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

Устинин Михаил Николаевич

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

Защита диссертации состоится 22 декабря 2011 г. в 1300 на заседании диссертационного совета Д 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%. Примечание. В качестве «аккуратности» в задаче распознавания вторичной структуры белка используется доля совпадений литер вторичной структуры (обозначается как «Q3total»).

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

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

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

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

Пусть заданы два алфавита: алфавит A для описания первичной структуры белка («верхнего слова») и алфавит B для описания вторичной структуры («нижнего слова»). Пусть A = {а1, а2, ..., аn(A)}, n(A)=|A| > 0 и B = {b1, b2, …, bn(B)}, n(B)=|B| > 0. Произвольное слово в алфавите А обозначим V=v1v2vn(V), в алфавите В - W=w1w2wn(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 , μ1< μ2< …<μm. Будем называть μi позициями. Параметр m назовем размерностью маски и будем обозначать как , а параметр μm - μ1 + 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.

  1   2   3

Похожие:

Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconПоясните методику исследования закономерностей вторичной электронной эмиссии
Нарисуйте и объясните графики зависимости коэффициента вторичной эмиссии от энергии и угла падения первичных электронов
Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconЛабораторная работа №5 Реализация алгоритма обнаружения нечетких дубликатов
Цель работы: научиться реализовывать на выбранном языке программирования алгоритмы обнаружения нечетких дубликатов на основе алгоритма...
Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconСтруктурный подход и принципы формирования примитивов в задаче распознавания...
Ый подход и принципы формирования примитивов в задаче распознавания составных объектов 1
Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconПрограмма по дисциплине ен ф. 1 «математика и информатика»
Аксиоматический метод, основные математические структуры, вероятность и статистика, математические модели, алгоритмы и языки программирования,...
Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconПрограмма дисциплины утверждаю
...
Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconФормализация лексического значения слова в задаче распознавания ситуаций...

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

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

Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconО возможности применения алгоритмов мгуа в задаче распознавания препятствий...
Томский Государственный Университет Систем Управления и Радиоэлектроники, Россия, г. Томск, 634050, пр. Ленина, д. 40, тел. 834-041,...
Модели и алгоритмы обнаружения локальных закономерностей в задаче распознавания вторичной структуры белка iconХалед Садек Математические модели и алгоритмы анализа и оптимизации...
Математические модели и алгоритмы анализа и оптимизации функционирования локальной компьютерной сети
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница