1) Обнаружение мотивов в наборе нуклеотидных или аминокислотных последовательностей (строк в алфавите {A, C, G, T}) с помощью частотного анализа коротких строк.
Для оценки выигрыша в скорости в решении биоинформационных задач при использовании суффиксных деревьев была проведена серия экспериментов. Эксперименты проводились на компьютере со следующими параметрами: процессор AMD Athlon II Neo K125, 1.70 ГГц; ОЗУ 2 Гб; ОС: Windows 7. В качестве входных данных взяты наборы случайных нуклеотидных последовательностей, сгенерированные с помощью сервиса “Random DNA sequence” на сайте “The Sequence Manipulation Suite” [6]. В качестве «модельных» были выбраны следующие задачи биоинформатики:
Оценка быстродействия
Дополнительные издержки на построение и хранение суффиксных деревьев приводят к тому, что в некоторых ситуациях алгоритмы, основанные на суффиксных деревьях, могут проигрывать по производительности более простым по структуре алгоритмам. Для практического применения процедур обработки длинных строк необходимо знать, для каких задач применение суффиксных деревьев действительно эффективно, а для каких задач они не дают эффекта. Результаты экспериментов вместе с описанием решаемых задач приведены в следующем разделе.
Помимо перечисленных выше достоинств, применение суффиксных деревьев в процедурах обработки строк обладает и недостатками, связанными с затратами времени на препроцессинг и затратами памяти для хранения суффиксного дерева. В некоторых случаях эти дополнительные затраты могут быть сокращены за счёт применения суффиксных деревьев ограниченной глубины [5].
Наиболее известные применения суффиксных деревьев связаны с исследовательскими проектами (например, проект Arabidopsis thaliana в Мичиганском университете и Университете Миннесоты и проект Saccharomyces cerevisiae (пивные дрожжи), выполняемом в Институте Макса Планка) или для решения отдельных вычислительных задач [1, 5].
Для решения задач, связанных с поиском в наборе строк, применяются т.н. «обобщённые» суффиксные деревья, представляющие суффиксы всех строк из заданного набора.
Для построения суффиксного дерева требуется выполнить предварительную обработку (препроцессинг) одной или нескольких обрабатываемых строк; после этого суффиксное дерево позволяет решать многие задачи очень быстро – за время, линейное от длины строки. К числу таких эффективно решаемых задач относятся задачи нахождения подстроки по заданному шаблону, наибольшей общей подстроки для нескольких строк, наибольших повторяющихся подстрок, уникальных подстрок и многие другие.
Рис. 1. Суффиксное дерево для строки «gatgac»
Суффиксное дерево [1] – это структура, предназначенная для быстрой обработки больших строк (последовательностей символов в некотором алфавите). «Физически» суффиксное дерево для m-символьной строки S – это ориентированное дерево с корнем, имеющее ровно m листьев, занумерованных от 1 до m. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки S (дуговой меткой). Никакие две дуги, выходящие из одной и той же вершины, не могут иметь пометок, начинающихся с одного и того же символа. Главная особенность суффиксного дерева заключается в том, что для каждого листа i конкатенация меток дуг на пути от корня к листу i в точности составляет суффикс строки S, начинающийся в позиции i. Например, суффиксное дерево для строки «gatgac» имеет следующий вид (рис. 1):
Суффиксные деревья
Работа проводилась при финансовой поддержке Министерства образования и науки Российской Федерации.
В данной статье представлено краткое описание использованных структур и результаты вычислительных экспериментов. Анализ результатов показывает, что для ряда задач применение суффиксных деревьев позволяет достичь значительного ускорения, а суффиксные деревья с ограничением глубины позволяют получить дополнительное ускорение. Однако есть задачи, для которых более эффективными оказываются «наивные» алгоритмы, не использующие суффиксные деревья.
В Южном федеральном университете в рамках проекта «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК» разработаны программные модули для решения ряда важный задач биоинформатики [1]. Для повышения скорости расчётов некоторые из процедур были реализованы на основе особой структуры данных – «суффиксных деревьев».
Многие задачи анализа геномных и протеомных данных требуют быстрой обработки большого количества длинных строк. К ним относятся, например, обнаружение мотивов (повторяющихся фрагментов в наборе последовательностей), поиск известных и предсказание новых регуляторных сайтов в последовательностях ДНК, сбор и анализ статистики по составу и расположению фрагментов в геноме или в аминокислотных последовательностях.
1. ФГАОУ ВПО «Южный федеральный университет»
Адигеев М.Г. 1, Бут А.А. 1
АНАЛИЗ ЭФФЕКТИВНОСТИ СУФФИКСНЫХ ДЕРЕВЬЕВ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ БИОИНФОРМАТИКИ
Технические науки
АНАЛИЗ ЭФФЕКТИВНОСТИ СУФФИКСНЫХ ДЕРЕВЬЕВ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ БИОИНФОРМАТИКИ - Технические науки - Современные проблемы науки и образования
Комментариев нет:
Отправить комментарий