«Биокомпьютеры»

Московская Государственная Академия Приборостроения иИнформатики
ДИПЛОМНАЯ РАБОТА
по информационным экономическим системам
«Биокомпьютеры»
Выполнил: Пяров Тимур Р
ЭФ2, 2 курс, 35.14
2002
Москва
Оглавление TOC o «1-3» h z u
Полностьюбио. PAGEREF _Toc10443777 h 3
ВГермании создан первый в мире нейрочип, сочетающий электронные элементы инервные клетки  PAGEREF _Toc10443778 h 4
Биологияin silico. PAGEREF _Toc10443779 h 5
Инфузорноепрограммирование. PAGEREF _Toc10443780 h 8
Биоалгоритмика. PAGEREF _Toc10443781 h 11
Биочипыкак пример индустриальной биологии. PAGEREF _Toc10443782 h 17

Первый биокомпьютер


Группе учёных из мюнхенского Института биохимии имени Макса Планка удалосьсоздать первый в мире нейрочип. Микросхема, изготовленная Питером Фромгерцом иГюнтером Зеком, сочетает в себе электронные элементы и нервные клетки.

Главной проблемой при создании нейрочипов всегда была сложность фиксациинервных клеток на месте. Когда клетки начинают образовывать соединения друг сдругом, они неизбежно смещаются. На этот раз учёным удалось избежать этого.

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

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

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

Впрочем, такие проекты пока остаются фантастикой. До их реализации пока ещёочень далеко, а пока главным предназначением устройств, подобных созданной вМюнхене нейросхеме, является изучение механизмов работы нервной системы ичеловеческой памяти.Полностью био
 
Группа ученых из Вейцмановского Института (Weizmann Institute), Израиль,удалось создать первый в мире компьютер, все обрабатываемые данные и компонентыкоторого, включая «железо», программы и систему ввода-вывода,умещаются в одной стеклянной пробирке. Фокус заключается в том, что вместотрадиционных кремниевых чипов и металлических проводников новый компьютерсостоит из набора биомолекул — ДНК, РНК и некоторых ферментов. При этомферменты (или, по-другому, энзимы) выступают в роли «железа», апрограммы и данные зашифрованы собой парами молекул, формирующих цепочки ДНК (наиллюстрации).

По словам руководителя проекта профессора Эхуда Шапиро (Ehud Shapiro),биокомпьютер пока может решать лишь самые простые задачи, выдавая всего дватипа ответов: «истина» или «ложь». При этом в однойпробирке помещается одновременно до триллиона элементарных вычислительныхмодулей, которые могут выполнять до миллиарда операций в секунду. Точность вычисленийпри этом составит 99,8%. Для проведения вычислений необходимо предварительносмешать в пробирке вещества, соответствующие «железу»,«программному обеспечению» и исходным данным, при этом ферменты, ДНКи РНК провзаимодействуют таким образом, что в результате образуется молекула, вкоторой зашифрован результат вычислений.

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



Главной проблемой при создании нейрочипов всегда была сложность фиксациинервных клеток на месте. Когда клетки начинают образовывать соединения друг сдругом, они неизбежно смещаются. На этот раз учёным удалось избежать этого.

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

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

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

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


Источник:
Nature Биология insilico 
Автор: Михаил Гельфанд, gelfand@integratedgenomics.ru
Дата публикации:21.09.2001


Вычислительнаябиология, она же биоинформатика, она же компьютерная генетика — молодая наука,возникшая в начале 80-х годов на стыке молекулярной биологии и генетики,математики (статистики и теории вероятности) и информатики, испытавшая влияниелингвистики и физики полимеров. Толчком к этому послужило появление в конце70-х годов быстрых методов секвенирования* последовательностей ДНК*. Нарастаниеобъема данных происходило лавинообразно (рис. 2) и довольно скоро стало ясно,что каждая полученная последовательность не только представляет интерес сама посебе (например, для целей генной инженерии и биотехнологии), но и приобретаетдополнительный смысл при сравнении с другими. В 1982 году были организованыбанки данных нуклеотидных последовательностей — GenBank в США и EMBL в Европе.Первоначально данные переносились в банки из статей вручную, однако, когда этотпроцесс начал захлебываться, все ведущие журналы стали требовать, чтобыпоследовательности, упоминаемые в статье, были помещены в банк самими авторами.Более того, поскольку секвенирование уже давно стало рутинным процессом,который выполняют роботы или студенты младших курсов на лабораторных работах,многие последовательности сейчас попадают в банки без публикации. Банкипостоянно обмениваются данными и, в этом смысле, практически равноценны, однакосредства работы с ними, разрабатываемые в Центребиотехнологической информации США и Европейскоминституте биоинформатики, различны. Пожалуй, первым биологически важнымрезультатом, полученным при помощи анализа последовательностей, былообнаружение сходства вирусного онкогена v-sis и нормального гена факторароста тромбоцитов, что привело к значительному прогрессу в понимании механизмарака. С тех пор работа с последовательностями стала необходимым элементомлабораторной практики.
Рис. 2.
Количество статей по молекулярной биологии в библиографической базе данных PubMed (красные ромбы) и количество фрагментов нуклеотидных последовательностей в базе данных GenBank (синие квадраты) по состоянию на 1982-2000 годы.
Шкала — логарифмическая, так что рост количества последовательностей — экспоненциальный.
Объем базы в нуклеотидах тоже растет экспоненциально.
В 1995 году был секвенирован первый бактериальный геном*, в 1997 — геномдрожжей. В 1998 было объявлено о завершении секвенирования генома первогомногоклеточного организма — нематоды 1. По состоянию на 1 сентября 2001 года доступны 55геномов бактерий, геном дрожжей, практически полные геномы Arabidopsisthaliana (растения, родственного горчице), нематоды, мухи дрозофилы — всеэто стандартные объекты лабораторных исследований. Уже два раза (весной 2000 изимой 2001 года) было объявлено о практическом завершении секвенирования геномачеловека — имеющиеся фрагменты действительно покрывают его более чем на 90%.Количество геномов,находящихся в распоряжении фармацевтических и биотехнологических компаний,оценить трудно, хотя, по-видимому, оно составляет многие десятки и даже сотни.Ясно, что подавляющее большинство генов в этих геномах никогда не будетисследовано экспериментально. Поэтому компьютерный анализ и становится основнымсредством изучения.
Все это привело к тому, что биоинформатика стала чрезвычайно модной областьюнауки, спрос на специалистов в которой очень велик. Следует отметить, что однимиз неприятных последствий возникшего шума стало то, что биоинформатикойназывают всё, где есть биология и компьютеры 2. В то же время многие области уже пережили такиемоменты (например, теория информации 3), и хочется надеяться, что за пеной ажиотажа непропадет то действительно интересное, что делается в настоящей биоинформатике.
Традиционно к биоинформатике относится:
§ 
§ 
§ 
§ 
Следует отметить, что многие задачи из разных областей решаются сходнымиалгоритмами, один из примеров этого приводится в статье М. А. Ройтберга.
В последние годы возник ряд новых задач, связанных с прогрессом в областиавтоматизации не только секвенирования, но и других экспериментальных методов:масс-спектрометрии, анализа белок-белковых взаимодействий, исследования работыгенов в различных тканях и условиях (см. статью И. А. Григорян и В. Ю. Макеевав этом номере). При этом не только возникает необходимость создавать изаимствовать из других областей новые алгоритмы (например, для обработки результатовэкспериментов в области протеомики* широко применяются методы анализаизображений), но и происходит распространение биоинформатических подходов насмежные области, например популяционную и медицинскую генетику. Существенно приэтом, что роль биоинформатики не сводится к обслуживанию экспериментаторов, какэто было еще несколько лет назад: у нее появились собственные задачи. Болееподробно об этом можно прочитать в обзоре (М. С. Гельфанд, А. А. Миронов.Вычислительная биология на рубеже десятилетий. Молекулярная биология. 1999, т.33, № 6, с. 969-984); можно упомянуть также сборник статей (Математическиеметоды для анализа последовательностей ДНК. М. С. Уотермен, ред. — М.: Мир,1999). Проект курса побиоинформатике, перечисляющий основные направления. Основные журналы побиоинформатике — «Bioinformatics», «Journal of Computational Biology» и«Briefings in Bioinformatics», конференции — ISMB (Intellectual Systems forMolecular Biology) и RECOMB (International Conference on ComputationalBiology).
Словарь
[i41320]
1 (обратнок тексту) — Вопрос о том, что такое полностью секвенированный геноммногоклеточного организма, нетривиален. В частности, значительную его часть(несколько процентов) составляют повторы, которые и вообще крайне сложны длясеквенирования. В таких областях находится мало генов, и поэтому их обычнооставляют «на потом». Текущее же состояние генома человека напоминаетрассыпанную мозаику, часть элементов которой отсутствует, а кроме того,подмешаны фрагменты других мозаик (посторонние последовательности).
2 (обратнок тексту) — В плане одного академического института на 2001 год в разделе«биоинформатика» можно было встретить, например, компьютерное моделированиесокращений сердечной мышцы — это очень интересная и уважаемая, но совершенноотдельная тема. А в университетском курсе биоинформатики предлагается изучать«Возможный механизм пунктурной терапии».
3 (обратнок тексту) — См. очень поучительную заметку Клода Шеннона «The Bandwagon»(Trans. IRE, 1956, ИТ-2 (1), 3, русский перевод в: К. Шеннон. Работы потеории информации и кибернетике. — М.: Изд-во иностранной литературы, 1963).Вот цитата: «Сейчас теория информации, как модный опьяняющий напиток, кружитголову всем вокруг. Для всех, кто работает в области теории информации, такаяпопулярность несомненно приятна и стимулирует их работу, но в то же время инастораживает… Здание нашего несколько искусственно созданного благополучияслишком легко может рухнуть, как только в один прекрасный день окажется, чтопри помощи нескольких магических слов, таких как информация, энтропия,избыточность… нельзя решить всех нерешенных проблем… На понятия теорииинформации очень большой, даже, может быть, слишком большой спрос. Поэтому мысейчас должны обратить особое внимание на то, чтобы исследовательская работа внашей области велась на самом высоком научном уровне, который только возможнообеспечить».
Словарь
ДНК (дезоксирибонуклеиновая кислота) — полимерная молекула,элементарными единицами которой являются четыре нуклеотида: A, C, G, T. Ген- участок ДНК, кодирующий один белок. Белок — полимер, в построениикоторого принимают участие 20 аминокислот (на самом деле больше, нодругие аминокислоты появляются в результате дополнительной химическоймодификации). Белки играют основную роль в жизни клетки — формируют ее скелет,катализируют химические реакции, выполняют регуляторные и транспортные функции.В живой клетке каждая молекула белка имеет сложную пространственную структуру(см. рис. 1).

Рис. 1. Схема биосинтеза белка.
РНК-полимераза синтезирует РНКовую копию (мРНК) фрагмента ДНК (транскрипция). Рибосома транслирует мРНК и осуществляет синтез белка, присоединяя аминокислоты в соответствии с таблицей генетического кода (см. рис. 1 к следующей статье). Затем белок сворачивается в пространственную структуру (об этом подробнее см. в КТ #398).
Геном — совокупность всех генов организма или, шире, полнаяпоследовательность ДНК. Размер генома человека — 3 миллиарда нуклеотидов,кодирующих 35-40 тысяч генов 1, генома бактерий — от 600 тысяч нуклеотидов/600генов (внутриклеточные паразиты) до 6-8 миллионов нуклеотидов/5-6 тысяч генов(свободно живущие бактерии). Упражнение: в скольких выпусках журнала«Компьютерра» можно будет опубликовать бактериальный геном, если посвящатьэтому половину каждого номера?
Секвенирование — определение последовательности нуклеотидов вофрагменте ДНК. Именно это имеется в виду, когда в газетах пишут о «расшифровкегенома человека». Исследование работы генов в масштабе целых организмов, атакже эволюция геномов составляют предмет геномики, а анализ полногонабора белков в клетке и их взаимодействий друг с другом — предмет протеомики 2.Инфузорноепрограммирование 



Вовторой декаде сентября в Праге прошла 6-я «Европейская конференция по искусственнойжизни» — междисциплинарный форум, на который собираются ученые, изучающиеприроду и перенимающие в своих исследованиях ее «творческий опыт».
Например, исследователи из голландского «Центра природных вычислений»при Лейденском университете полагают, что, освоив некоторые приемы генетическихманипуляций, заимствованные у простейших одноклеточных организмов — ресничныхинфузорий, человечество сможет воспользоваться гигантским вычислительнымпотенциалом, скрытым в молекулах ДНК.
Ресничные обитают на Земле, по меньшей мере, два миллиарда лет, ихобнаруживают практически повсюду, даже в самых негостеприимных местах. ДиректорЦентра Гжегож Розенберг (Grzegorz Rozenberg), называет эти инфузории «одним изнаиболее успешных организмов на Земле». Ученые объясняют такую «удачливость»чрезвычайно эффективными механизмами манипуляции собственной ДНК, позволяющимиинфузориям приспосабливаться практически к любой среде обитания.
Уникальность ресничных в том, что их клетка имеет два ядра — одно большое,«на каждый день», где в отдельных нитях хранятся копии индивидуальных генов; иодно маленькое, хранящее в клубке используемую при репродукции единственнуюдлинную нить ДНК со всеми генами сразу. В ходе размножения «микроядро»используется для построения «макроядра» нового организма. В этом ключевомпроцессе и происходят чрезвычайно интересные для ученых «нарезание» ДНКмикроядра на короткие сегменты и их перетасовка, гарантирующие то, что вмакроядре непременно окажутся нити с копиями всех генов.
Розенбергом и его коллегами установлено, что способ, с помощью которогосоздаются эти фрагменты, удивительно напоминает технику «связных списков»,издавна применяемую в программировании для поиска и фиксации связей между
Напомним, что в 1994 году Леонардом Эдлманом (Leonard Adleman)экспериментально было продемонстрировано, как с помощью молекул ДНК вединственной пробирке можно быстро решать классическую комбинаторную «задачупро коммивояжера» (обход вершин графа по кратчайшему маршруту), «неудобную» длякомпьютеров традиционной архитектуры. Результаты же экспериментов ученых излейденского центра дают основания надеяться, что в недалеком будущем ресничныеинфузории можно будет использовать для реальных ДНК-вычислений.
А вот английские исследователи из компании British Telecom пришли к выводу,что изучение поведения колоний бактерий дает ключ к решению сложнейшей задачиупорядочивания коммуникационных сетей.
Для описания ближайшего будущего компьютеров сегодня все чаще привлекаютпопулярную концепцию «всепроникающих вычислений» — идею о гигантской совокупностимикрокомпьютеров, встроенных во все предметы быта и незаметно взаимодействующихдруг с другом. В этой единой беспроводной сети будет увязано все: кухоннаятехника, бытовая электроника, следящие за микроклиматом сенсоры в комнатах,радиомаяки на детях и домашних животных… Список этот можно увеличиватьбесконечно. Но сейчас добавление каждой новой «умной штучки» отнимает массувремени, чтобы взаимно подстроить работу этого устройства и ужесформировавшейся конфигурации. В концепции же будущего, поскольку хозяева дома,по определению, не обладают ни временем, ни знаниями для настройки совместнойработы всей этой армии бесчисленных «разумных вещей», изначально предполагаетсяспособность системы к самоорганизации. Поэтому достаточно 1, способна поддерживать работу сети из несколькихтысяч устройств, автоматически управляя большими популяциями отдельныхэлементов.
Для симуляции функционирования такой колонии британскими учеными быласоздана сеть из трех тыс. узлов. Основой самоорганизации стало присвоениеразличных приоритетов рассылаемым по сети пакетам данных. Например, высшийприоритет получили «информационные» пакеты, доносящие послания от одного узла кдругому (кроме них в системе рассылаются еще «управляющие», «конфигурирующие» ипрочие пакеты), поэтому ими занимаются устройства, имеющие в данный моментнаилучшие связи с максимальным числом элементов сети.
В British Telecom полагают, что воплощение экспериментальной концепции вреальных продуктах можно ожидать уже через пять-шесть лет.
Еще одна любопытная разработка была представлена на конференции бельгийскимиисследователями под руководством профессора Марко Дориго (Marco Dorigo). Онипродемонстрировали, что программы, имитирующие стратегию поведения муравьиногосообщества, могут успешно управлять работой сложных компьютерных сетей.
Рыская в поисках корма, муравьи-разведчики оставляют за собой меченуюферомонами дорожку. При этом зачастую к одному источнику пищи прокладываетсясразу несколько троп, но разведчик, открывший самую короткую тропинку,возвращается быстрее и уводит за собой соплеменников. Выделяемые ими феромоныделают
Практические испытания проводились в сетях Национального научного фонда СШАи японской корпорации NTT. Синтетические «муравьи» должны были, ничего не знаяо конфигурации сети, отыскать кратчайшую дорогу от одного узла к другому.Быстро исследовав сеть, агенты определили её строение и вскоре уже могли«подсказать» любому информационному пакету к какому следующему узлу ему нужнонаправиться, чтобы достичь своей цели быстрее. Иначе говоря, был реализованмеханизм высококачественного интеллектуального роутинга, причем привозникновении различных «заторов» в сети «искусственные муравьи»реконфигурировали схему роутинга быстрее, чем традиционные решения.
Как считают авторы, их разработка может использоваться и для выполнениядругих неординарных задач, например динамической организации снабжения товаромв сложной торговой сети. Биоалгоритмика 



Этазаметка посвящена разделу биоинформатики, который можно назвать«биоалгоритмикой», — алгоритмам анализа первичных структур(последовательностей) биополимеров. Биоалгоритмика находится на стыкеприкладной теории алгоритмов и теоретической молекулярной биологии и, подобнодругим разделам биоинформатики, бурно развивалась в течение 70-х — 90-х годовXX века 1.
Алгоритмы анализа символьных последовательностей и связанные с нимиалгоритмы сортировки и алгоритмы на графах активно изучались и разрабатывались,начиная со второй половины 50-х годов. Алгоритмический бум 60-х — 70-х годовбыл связан как с разработкой теоретических моделей вычислений (конечныеавтоматы и их варианты с различными видами памяти), так и с появлениемкомпьютеров и, следовательно, реальной потребностью в обработке значительных(по тем временам) объемов данных. Своеобразными итогами этого периода сталимноготомное «Искусство программирования» Д. Кнута (1968-1973) и «Построение ианализ вычислительных алгоритмов» А. Ахо, Дж. Хопкрофта и Дж. Ульмана (1976).Анализ достижений этого замечательного этапа в развитии теории алгоритмов естьтакже в книге: В. А. Успенский, А. Л. Семенов. Теория алгоритмов: основныеоткрытия и приложения. — М.: Наука, 1987.
Таким образом, к моменту создания первых баз данных последовательностей ДНКи белков — началу 80-х годов — алгоритмический аппарат был, в значительнойстепени, готов. При этом специалисты в области алгоритмов рассматривалибиологические приложения в одном ряду с техническими, одни и те же алгоритмыприменялись, например, для сравнения («выравнивания») биологическихпоследовательностей и для поиска сбоев при хранении файлов. Характерно название первого сборника работ по биоалгоритмике — «Time Warps, String Edits, andMacromolecules: The Theory and Practice of Sequence Comparison» (Sankoff, D andKruskal, JB, eds, 1983).
Впрочем, довольно скоро выяснилось, что анализ биологическихпоследовательностей имеет свою специфику — прежде всего с точки зренияпостановок задач. Вот, например, задача о распознавании «вторичной» структурыРНК. Она очень важна для молекулярной биологии и впервые была рассмотрена еще вконце 70-х годов. Молекула рибонуклеиновой кислоты (РНК) — однонитевой полимер,состоящий из четырех видов мономеров-нуклеотидов (аденин, гуанин, урацил,цитозин). А-У и, соответственно, Г-Ц могут образовывать водородные связи,стабилизирующие молекулу. Однако образование одних связей из-застереохимических соображений делает невозможным образование других, то есть невсе комбинации межнуклеотидных связей в молекуле РНК допустимы (правилаконфликтов между связями известны). Требуется для данной нуклеотиднойпоследовательности найти наиболее стабильную вторичную структуру, т. е.допустимый набор межнуклеотидных связей, содержащий наибольшее возможноеколичество элементов (рис. 1). Эта задача может быть переформулирована какзадача построения графа (точнее — гиперграфа, см. ниже) специальноговида с максимально возможной суммой весов ребер (вершины соответствуютнуклеотидам, ребра — установленным связям) и решена с помощью метода динамическогопрограммирования (Ruth Nussinov и соавт., 1978; также см. гл. 7 в книге М.Уотермена). Однако появляющиеся ограничения на вид графа весьма экзотичны сточки зрения небиологических приложений. Другой пример задачи, не имеющейсмысла вне биологического контекста, -распознавание кодирующих фрагментов ДНК,рассмотренное в статье Михаила Гельфанда.

Рис. 1.Вторичная структура участка бактериофага Qb (231 основание). Сплошные линии проведены между парами оснований, связанных водородными связями.
(По книге М. С. Уотермен (ред.). Математические методы для анализа последовательностей ДНК. — М.: Мир, 1999.)
Возвращаясь к задаче распознавания наиболее стабильной «вторичной» структурыРНК, отметим следующие обстоятельства, характерные для многих важных задачбиоалгоритмики:
§ 
§ 
§ 
§ 
Специфика биоалгоритмики, однако, проявляется не только в задачах, которые«по определению» не могли встретиться вне анализа биологическихпоследовательностей. Показательна самая старая и, наверное, самая популярнаязадача анализа биологических последовательностей — их выравнивание. Выравнятьдве последовательности — это изобразить их друг над другом, вставляя в обепробелы так, чтобы сделать их длины равными. Вот, например, как можновыровнять слова ПОДБЕРЕЗОВИК и ПОДОСИНОВИК (cм. врезку).
Такой способ изображения последовательностей широко распространен вмолекулярной биологии. Предполагается, что выравнивание отражает эволюционнуюисторию, то есть стоящие друг под другом символы соответствуют одному и тому жесимволу последовательности-предка. К сожалению, мы не знаем, как именно шлаэволюция последовательностей. Поэтому в качестве «правильного» обычновыбирается выравнивание, оптимальное относительно некоторой функции качества.Но как мы можем контролировать правильность выбора этой функции? Есть ли у нас(пусть приблизительные) «эталоны»? К счастью, да. В качестве эталонных можновзять выравнивания, соответствующие наилучшему возможному совмещению ихпространственных структур (такие структуры известны для нескольких сотенбелков). Это связано с тем, что функционирование белка в клетке определяетсяпрежде всего его пространственной структурой и можно ожидать, что аминокислоты,лежащие в сходных местах трехмерной структуры, соответствуют одним и тем жеаминокислотам предкового белка.
В «добиологическом» анализе последовательностей (например, при сравнениифайлов) использовалось понятие редактирующего расстояния. При этомфиксируется набор редактирующих операций (например, замена символа, вставкасимвола и удаление символа) и для каждой операции фиксируется цена. Тогдакаждое выравнивание получает свою цену, определяемую как сумма цен отдельныхопераций.
Лучшим считается то, которое имеет наименьшую цену. Например, при ценезамены 1 и цене вставки/удаления 3, лучшими в примере во врезке 2 будут третьеи четвертое выравнивания, а при цене замены 10 и той же цене вставки/удаления,лучшим будет пятое.
Довольно скоро выяснилось, что для выравнивания биологических последовательностейв эту естественную схему необходимо внести ряд важных изменений. Дело в том,что разные аминокислоты различны по-разному. Например, аланин и валин оченьпохожи по своим свойствам (и цена замены аланина на валин должна бытьнебольшой), и они оба совершенно не похожи на триптофан. Более того, дажеодинаковые аминокислоты «одинаковы по-разному». Так, триптофан — редок, исопоставление двух триптофанов более ценно, чем сопоставление весьмараспространенных аланинов.
Поэтому вместо «цены замены символа» в схеме редактирующего расстояния присравнении белков используется весовая матрица замен, где каждой паресимволов соответствует вес (положительный — для похожих, отрицательный длянепохожих), а выравниванию в целом — вес W=R-G, где R — суммарныйвес сопоставлений символов (в соответствии с выбранной весовой матрицей замен),G — суммарный штраф за удаления и вставки символов. Такимобразом, оптимальное выравнивание — это выравнивание, имеющее наибольший вес(в то время как цена требовалась наименьшая). Например, пусть вессовпадения для гласных букв +2, вес совпадения для согласных букв +1, вессопоставления двух различных гласных или двух различных согласных -1, вессопоставления гласной и согласной -2. Далее, пусть штраф за удаление иливставку символа -5. Тогда, например, третье выравнивание имеет вес -3, ачетвертое — +1. Таким образом, оптимальное выравнивание слов ПОДБЕРЕЗОВИК иПОДОСИНОВИК (при выбранных матрице замен и штрафе за удаление/вставку) — четвертое. Переход от минимизации цены к максимизации качества, — это не только технический трюк. На языке максимизации качества естественноставится задача о поиске оптимального локального сходства. Эта задачасоответствует сравнению двух белков, которые в ходе эволюции стали совсемнепохожи — везде, кроме относительно короткого участка.
Алгоритм построения оптимального выравнивания основан на методединамического программирования, введенном в широкую практику Ричардом Беллманомв 1957. Идея метода состоит в следующем: чтобы решить основную задачу, нужнопридумать множество промежуточных и последовательно их решить (в каком порядке- отдельный вопрос). При этом очередная промежуточная задача должна «легко»решаться, исходя из уже известных решений ранее рассмотренных задач. Множествопромежуточных задач удобно представлять в виде ориентированного ациклическогографа. Его вершины соответствуют промежуточным задачам, а ребра указывают нато, результаты решений каких промежуточных задач используются для основной.Таким образом, исходная задача сводится к поиску оптимального пути в графе 2 (подробнее о методе динамического программированиясм. книгу Ахо, Хопкрофта и Ульмана, а также статью Finkelstein A.V., Roytberg M.A. Computation ofbiopolymers: a general approach to different problems. Biosystems.1993;30 (1-3): 1-19.). Аналогично можно переформулировать различные варианты задачвыравнивания, предсказания вторичной структуры РНК и белков, поискабелок-кодирующих областей ДНК и других важных проблем биоинформатики.
При построении оптимального выравнивания (мы рассматриваем простейшийслучай, когда удаление и вставка отдельных символов штрафуются независимо)промежуточные задачи — это построение оптимальных выравниваний начальныхфрагментов исходных последовательностей. При этом задачи нужно решать в порядкевозрастания длин фрагментов. Граф зависимости между промежуточными решениямидля сравнения слов «ПАПКА» и «ПАПАХА», а также последовательность промежуточныхшагов, приводящих к оптимальному выравниванию, показаны на рис. 2.
Рис. 2.

(a) Граф зависимостей между промежуточными задачами для выравнивания слов ПАПКА и ПАПАХА. Каждая вершина соответствует паре начальных фрагментов указанных слов. Диагональное ребро, входящее в вершину, соответствует сопоставлению последних букв сравниваемых начальных фрагментов (случай 1), горизонтальное ребро — удалению буквы в слове ПАПАХА, вертикальное ребро — удалению буквы в слове ПАПКА (случаи 2 и 3). Правая верхняя вершина — начальная и соответствует выравниванию пустых слов, левая нижняя вершина — конечная, соответствует выравниванию полных слов ПАПКА и ПАПАХА.

(b) Оптимальное выравнивание слов ПАПКА и ПАПАХА при следующих параметрах: вес совпадения букв: 1, штраф за замену гласной на гласную или согласной на согласную: 1, штраф за замену гласной на согласную или согласной на гласную: 2, штраф за удаление символа: 3.

(c) Траектория, соответствующая оптимальному выравниванию. В клетках указаны веса промежуточных оптимальных выравниваний. Например, вес оптимального выравнивания для «ПАП» и «ПАПА» равен 0, а для «ПАПК» и «ПАПАХ» равен -1.
На двух примерах — распознавания вторичной структуры РНК (бегло) ивыравнивания белковых последовательностей (более подробно) мы проследили заэволюцией постановок задач в биоалгоритмике. Упомянем кратко еще несколькоаспектов. Пожалуй, с практической точки зрения самым важным является поиск вбазах данных последовательностей, сходных с изучаемой. Определяющую рольначинают играть проблемы вычислительной эффективности, решаемые, в частности, сприменением алгоритмов хеширования. Для предсказания пространственной структурыбелков важны алгоритмы выравнивания последовательности со структурой (при этомиспользуется тот факт, что из-за разницы физико-химических свойств аминокислотывстречаются с разной частотой на поверхности белка и в структурном ядре).Наконец, мы полностью оставили в стороне задачи построения эволюционныхдеревьев по белковым последовательностям. Подчеркнем, что во всех случаяхпро