Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
В ряде работ(Ро!пег et al.,1984; Durand,Bregegere,1984; Dix,Kieronska,1988) удалось снизить трудоемкость перебора благодаря усовершенствованиям алгоритма Пирсона (эти методы применимы в основном для случая линейных молекул). Ноланом и др.(Nolan et al.,1984) предложен принципиально новый алгоритм перебора вариантов, применимый как для линейных, так и для кольцевых молекул (в работах Туффери и flp.(Tuffery et al.,1988), Беллона(Ве11оп,1988) и KpaB4aKa(Krawczak,1988) метод Нолана и др. был значительно усовершенствован). Совсем HeflaBHo(Goldstein, Waterman,1987) для построения физических карт был предложен метод, использующий интерпретацию задачи физического картирования в терминах статистической механики. Решение вопроса о том, какой из известных алгоритмов физического картирования является предпочтительным, затруднено, так как в настоящее время не представляется возможным теоретически оценить их вычислительную сложность (попытки анализа сложности, предпринятые в работе Полнера и др.(Ро1пег et al.,1984), привели к большому разрыву между верхней и нижней оценкой).
Построение множественных физических карт. Уже в первых работах по физическому картированию было отмечено, что использование только информации о результатах двух одиночных и одной совместной рестрикции, как правило, не дает возможности однозначно восстановить физическую карту: при числе сайтов около 10 ( по каждой рестриктазе) получаются десятки (а
иногда сотни) карт, лежащих в пределах ошибок биохимического эксперимента ( Певзнер, Миронов,1987а). Причины этого кроются, с одной стороны, в недостаточно высокой точности определения размеров фрагментов, с другой - в огромном количестве вариантов взаимного расположения сайтов рестрикции. Для снятия неоднозначности приходится переходить от двух к нескольким рестриктазам ( известны случаи, когда использование даже 5 одиночных и 10 совместных рестрикций не давало возможности однозначно идентифицировать физическую карту). Таким образом, при переходе к нескольким рестриктазам вместо классической задачи построения парной физической карты (по двум SD- и одной DD- рестрикции) возникает задача построения множественной физической карты (по нескольким SD- и DD-рестрикциям), для решения которой предложен метод потенциалов (Певзнер,Миронов,1987а). В разделе 5.4 описывается метод потенциалов и обсуждаются трудности, возникающие при построения множественных физических карт.
Уточнение физических карт. При реализации алгоритмов физического картирования на первый план выдвигаются следующие две задачи:
- оптимальная организация перебора гипотез о взаимном расположении сайтов (рассматривается в разделах 5.3 и 5.4);
- эффективная проверка и отбраковка гипотез о взаимном расположении сайтов.
В рассматриваемом ранее примере мы отвергли гипотезу о порядке расположения сайтов рестриктаз HindiII и BamHI, поскольку получающийся при принятии этой гипотезы набор размеров фрагментов совместной рестрикции S,=( 12,5, 7,7, 2,6, 2,2, 1,2, 0,3) совершенно не похож на экспериментально полученный набор S2=(10,9, 7,7, 4,8,
2,7, 0,3, 0,1). Однако, как правило, вопрос о принятии (или отбрасывании) той или иной гипотезы (или, иначе, о сходстве наборов размеров фрагментов) далеко не всегда решается столь однозначно: во-первых, экспериментально полученные размеры фрагментов совместной рестрикции определены с ошибками, а во-вторых, может оказаться, что рестрикционные сайты HindiII и BamHI можно "немножко подвигать" и наборы S, и S2 станут похожи? В разделе 5.5 рассматривается задача о проверке и отбраковке гипотез (другое ее название - уточнение физических карт, так как проверка гипотез сводится, как правило, к уточнению положения сайтов рестрикции относительно некоторой точки на карте - начала отсчета).
Еще в 1978 г. (Schroeder.Blattner,1978) был предложен метод наименьших квадратов для уточнения физических карт, при этом соответствие гипотезы о расположении сайтов экспериментальным данным оценивалось в евклидовой норме(см. раздел 5.5). Такой подход позволяет предложить быстродействующий алгоритм уточнения физических карт, однако использование евклидовой нормы для оценки гипотез не отбраковывает многие несостоятельные варианты. Выбор равномерной нормы в большей степени соответствует реальной задаче картирования, так как незначительные отклонения от данных электрофореграмм вполне допустимы (они постоянно встречаются при картировании), а вот значительные отклонения хотя бы на одном фрагменте недопустимы и должны приводить к отбраковке гипотезы о порядке расположения сайтов.
Рассмотрение задачи уточнения физических карт в равномерной норме (Певзнер,1987,1988а) приводит к двум известным задачам дискретной математики: нахождению циркуляций в потоковой сети с двусторонними ограничениями (Форд,Фалкерсон,1966) и поиску оптимального контура в графе (Karp, 1978). Использование алгоритмов Форда-Фалкерсона и Карпа дает возможность получить быстродействующий (что особенно важно, учитывая огромное число перебираемых гипотез) полиномиальный алгоритм уточнения физических карт. Помимо эффективного метода проверки и отбраковки гипотез, такой подход позволяет локализовать для каждой гипотезы узкие места, т.е. выявить фрагменты, дающие максимальное отклонение от экспериментальных данных(положение таких фрагментов может быть определено с привлечением дополнительных биохимических экспериментов).
