Математическая биофизика клетки - Иваницкий Г.Р.
Скачать (прямая ссылка):
В первых работах [118, 119] на основе последовательности случайных чисел строилась одна или несколько статистических последовательностей четырех символов. Исследовалась возможность однозначной реконструкции нуклеотидных последовательностей по перекрывающимся фрагментам, полученным расщеплением четырьмя, тремя или двумя ферментами, специфичными к одному символу каждый.
Были предприняты попытки создания компьютерных алгоритмов для построения нуклеотидных и белковых 1 последователь-
1 Следует заметить, что математическая задача восстановления последовательностей аминокислот в белках, в принципе, аналогична задаче восстановления последовательности нуклеотидов. Но для реальных белков задача
ностей из перекрывающихся продуктов полных гидролизов [122— 125]. Построение нуклеотидной последовательности осуществляется в этих алгоритмах путем полного перебора всех возможных последовательностей перекрывающихся продуктов, что требует очень больших затрат машинного времени.
Еще в 1959 г. Розен обратил внимание на то, что первичная структура биополимеров может быть описана в виде слова в определенном алфавите, и указал на возможность применения здесь понятий теории свободной полугруппы [120, 121]. Эта идея была использована в работе [126]. Задача о построении последовательности перекрывающихся продуктов двух полных гидролизов может быть интерпретирована также в терминах теории графов, (задача о построении эйлерова пути) [127].
Ниже рассмотрен математический подход к установлению первичной структуры нуклеиновых кислот.
11.2. Математическая постановка проблемы
Формулировка задачи в виде восстановления слов
Структуру биополимера будем рассматривать как слово в некотором алфавите. Отдельным фрагментам, которые получаются гидролизом (полным или частичным), соответствуют подслова определяемого слова. Для наглядности изложения будем пользоваться геометрическим представлением слов. На рис. 121 показан фрагмент молекулы 5SPHK Е. coli в виде двух разбиений с помощью нуклеаз на подслова. Одно из разбиений соответствует гидролизу панкреатической рибонуклеазой (подслова xt), другое— рибонуклеазой Т1 (подслова jjj).
Введем основные определения. Подслово х2 является перекрытием подслов у2 и Уз, подслово х3 — перекрытием подслов у3 и у4 и т. д. Пусть yj = diXjbi, тогда части подслов at и bt называются граничными, а подслово х} — внутренним для подслова у}. Например, подслово является внутренним для подслова у4.
Задачу восстановления слова можно сформулировать следующим образом. Пусть Н — набор произвольных подслов. Найти: а) условия существования, б) единственности и в) способ построения некоторого слова z, для которого подслова из набора Нг, принадлежащего Н, образуют единую последовательность перекрывающихся подслов, а остальные подслова набора Н являются внутренними подсловами подслов из набора Н\.
эта не является сложной, так как белковые цепи построены из 20 типов структурных единиц, а не из четырех, как нуклеиновые кислоты, при одинаковой или даже меньшей длине белковых цепей.
Z =
G U А О С О С С Б A U G О U A G
Рис. 121. Два полных гидролиза фрагмента молекулы 5S РНК Е. coli в виде наборов подслов
Н, Н2 2тег
J i I
$
и с с 8 и А G С е С Б С и с с с и и Т
1
и с в Б и А G С е С Б Г и с Г Г и и I
и с G Б и А С Б Г Гг Г и Г Г Г. и 1/ I
\
X X е и А Б с Гг С Г X X X X X X
\
и с Б X и А С с Б Г Б Г и Г Г с и и I
Рис. 122. Исходная информация в виде графов (два полных гидролизата фрагмента тРНК)
а — исходное слово; б — два разбиения слова: разрыв по буквам U и С и разрыв по букве G; в — отбрасывание внутренних подслов; г — граф подслов (задача Гамильтона); в — граф перекрытий; подслов (задача Эйлера)
Обычно накладывается ограничение на искомую последовательность: она должна содержать определенное число каждой из букв.
Прежде чем дать решение этой задачи, покажем, как ее можно сформулировать на другом математическом языке.
Формулировка задачи в терминах теории графов
Для каждого подслова из Н выберем все подслова yj, с которыми подслово х( перекрывается справа, перекрытие подслов xt и yj соответствует бинарному отношению А = {(хг, yj)} на множестве Н, такому, что в А входят пары элементов, соответствующие перекрывающимся подсловам.
Любое бинарное отношение на множестве Н может быть изображено в виде матрицы или в виде ориентированного графа [135, 136, 139].
Подсловам можно поставить в соответствие множество вершин графа. Если подслово, соответствующее хь перекрывается справа с подсловом, соответствующим ys, то вершины и yj соединяются направленным ребром, идущим из xt в yj. На ребрах указываются буквы, по которым происходит перекрытие. Проведение зтой процедуры для всех точек приводит к построению ориентированного графа, соответствующего бинарному отношению А (рис. 122). Построению последовательности всех перекрывающихся подслов соответствует построение в ориентированном графе пути, проходящего в направлении ребер через все вершины по одному разу. Такой путь в графе называется гамильтоновым путем (или циклом, если путь замкнут). Впервые задача о поиске гамильтонова цикла была поставлена в 1877 г., однако до сих пор нет эффективной процедуры нахождения гамильтонова пути в произвольном графе и методов доказательства существования такого пути. У известных алгоритмов сложность вычислений (число элементарных операций) определения гамильтонова цикла растет, как экспонента числа вершин. Это связано с перебором большого числа вариантов движения по графу.
