Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
транскрипции соответствует (8-4+1)•(21-15+1)=35 разных положений промоторной модели. Выбор правильного положения осуществлялся при помощи статистической матрицы узнавания Муллигана (Mulligan et al., 1984), Множество Y, формировалось только из i-й последовательности и включало в себя все другие положения промоторной структуры на последовательности.
В результате работы программы разделение оказалось невозможным. Это означает, что часто используемая классическая структура промотора (два блока по шесть нуклеотидов и вариабельное расстояние между ними) принципиально недостаточна для распознавания.
Чтобы решить задачу распознавания, необходимо было ввести новые признаки, например увеличить -10 и -35 области. Размер этих блоков был увеличен соответственно до одиннадцати и десяти нуклеотидов. Нетрудно подсчитать, что с учетом семи возможных значений расстояния между блоками число бинарных признаков стало равным N=4*11+4*10+7=91. В таком пространстве была найдена разделяющая гиперплоскость.
Из только что сказанного видно, что признаки были выбраны достаточно произвольно; можно было бы образовать другое похожее пространство признаков, например еще больше расширить -10 и -35 области и шйти другой обобщенный портрет промотора. Было бы интересно установить минимальный набор признаков, позволяющих построить разделяющий вектор и посмотреть, как меняется качество обучения при изменении пространства признаков.
Для оценки качества обучения можно пользоваться как теоретической оценкой, так и проверкой разделяющего вектора на контрольной выборке. В целях экономии машинного времени удобнее вычислять качество разделения при помощи теоретической формулы. По этой формуле разделяющий вектор считается более надежным, если он получен при помощи меньшего количества признаков, большей обучающей выборки и обеспечивает большее расстояние между разделяемыми множествами.
Определить оптимальное (с наилучшим качеством разделения) или ми-
Р и с. 4.9. Разделение
множеств несколькими способами: разделяющие векторы и
соответствующие им гиперплоскости могут заметно отличаться
Метод "обобщенный портрет" строит вектор f0, максимизирующий расстояние г между множествами, персептрон выдает первый попавшийся разделяющий вектор f
нимальное (с минимальной размерностью, позволяющей разделить множества) пространство признаков простым перебором не представляется возможным из-за огромного количества комбинаций. Пришлось отказаться от поиска глобального оптимума и использовать пошаговую процедуру, приводящую к локальному оптимуму. Выбрасывая из первоначального набора по одному наименее информативному признаку, можно получить минимальное пространство, дальнейшее уменьшение которого сделает невозможным распознавание на обучающей выборке.
После проведенной таким образом минимизации количества признаков, используемых при распознавании промоторов E.coli, выяснилось, что для разделения обучающей выборки достаточно учитывать всего 12 позиций в расширенных блоках Прибноу и Гильберта. Таким образом, количество признаков по сравнению с каноническим набором (оба блока по шесть нуклеотидов), который не позволил получить разделяющего вектора, не увеличилось. Позиции, учитываемые минимальным набором признаков, конечно, отличаются от позиций канонических блоков Прибноу и Гильберта, хотя и включают в себя некоторые наиболее важные из них.
Однако не стоит стремиться к сильному сокращению признаков, так как, разделяя стопроцентно обучающие множества, минимальный набор плохо работает на контрольной выборке. Очевидными недостатками обладает и слишком большой набор признаков - в него включаются незначимые признаки, делающие распознавание в значительной степени случайным. Существует некоторое оптимальное пространство признаков, которое можно найти, осуществляя пошаговую процедуру минимизации до тех пор, пока теоретическая оценка качества обучения не достигнет максимума.
Проверка алгоритма осуществлялась разбиением всей выборки промоторов на две группы: обучающую и контрольную, в каждой по 40 последовательностей. После того, как разделяющий вектор был построен на первой группе, с его помощью искали промоторы на второй группе последовательностей. Промотор считался найденным правильно, если блок Прибноу ТАТААТ находился на расстоянии четырех-восьми оснований от первого транскрибируемого нуклеотида. В оптимальном пространстве признаков алгоритм обобщенный портрет ошибся 4 раза, показав несколько лучший результат, чем статистическая матрица Муллигана (Mulligan et al., 1984), причем возможности алгоритма обобщенный портрет для анализа нуклеотидных последовательностей еще не исчерпаны.
4.6. МНОЖЕСТВЕННОЕ ВЫРАВНИВАНИЕ
Рассматривая выше обучающие выборки, мы считали,что последовательности уже выровнены и похожие участки расположены друг под дру-
гом; нам оставалось только подсчитать количество нуклеотидов в каждой позиции сайта. Оказывается, однако, что выровнять несколько последовательностей - очень сложная и неоднозначно решаемая проблема. Если мы будем отталкиваться от разных вариантов выравниваний, то, возможно, будем получать отличающиеся решающие правила. Экспериментальными методами, как правило, не удается выявить более предпочтительный вариант выравнивания. Перебор же всех возможных варианте-; потребует очень много времени. Так, если предположить, что блоки -1C и -35 в промоторах E.coli могут быть разделены 15-21 нуклеотидами, ь, расстояние от точки транскрипции до блока -10 изменяется в пределах четырех-восьми нуклеотидов, то число возможных положений этой структуры на последовательности с известной точкой начала транскрипции будет равно 35, а число разных вариантов выравниваний для выборки иг-200 промоторов достигнет 35200. При этом для каждого варианта нужно построить матрицу и определить качество распознавания - критерии оптимальности выравнивания. Ясно, что нужно придумать какой-то более, быстрый способ нахождения оптимального выравнивания.
