Geum.ru

В. Ю. Попов уральский государственный университет имени А. М. Горького, Екатеринбург задача

Вид материалаЗадача
Подобный материал:

УДК 004(06) Информационные технологии


Д.В. КОРНЕВ, В.Ю. ПОПОВ

Уральский государственный университет имени А.М. Горького, Екатеринбург


ЗАДАЧА ПОИСКА ПОДСТРОКИ В СТРОКЕ

В БИОИНФОРМАТИКЕ


В данной статье описывается исследование модификации алгоритма Бойера-Мура в приложении к задачам биоинформатики.


Задача поиска подстроки в строке имеет большое практическое значение с точки зрения биоинформатики. В частности, необходимость решения этой задачи возникает при поиске в ДНК участков, кодирующих белки. Вообще говоря, для нахождения подстроки в строке известно немало достаточно эффективных алгоритмов, однако объемы информации, которую необходимо обрабатывать и анализировать, велики, так размер одной ДНК человека составляет около 1.6 гигабайт [1]. Поэтому возникает необходимость в более эффективных алгоритмах.

В классическом варианте алгоритма Бойера-Мура [2] происходит последовательное сравнение подстроки и строки от последней буквы подстроки к первой. При несовпадении происходит сдвиг подстроки относительно строки, затем сравнение происходит вновь. Известны модификации, которые заключаются в изменении порядка сравнения букв. Они могут привести к уменьшению числа сравнений, что будет означать увеличение скорости поиска. Однако все эти модификации основаны на рассмотрении детерминированных правил, которые по сути дела не зависят от обрабатываемого массива информации. При этом известно, что для любой последовательности сравнений существует массив информации, на котором она будет наихудшей.

Поиск оптимального порядка сравнения для конкретного массива информации (например, база ДНК), является сложной комбинаторной задачей. Так, например, если взять, подстроку длиной 40 байт и ДНК длиной 1.6 мегабайт, то для нахождения наилучшего порядка сравнения на суперкомпьютере Томского государственного университета «СКИФ Cyberia» [3] (четвертый по мощности суперкомпьютер в России на ноябрь 2007 года [4]) потребуется 2е36 лет. Даже если полагаться на закон Мура [5], то до того времени, когда эта задача станет решаться менее чем за 1 минуту, придется ждать свыше 100 лет.

Нами были произведены вычисления на вышеупомянутом суперкомпьютере [3] для решения этой задачи в случае подстрок малой размерности. В результате было установлено, что на всех образцах прямой порядок сравнения приводил к наихудшим результатам. Классический обратный порядок был близок к наилучшему, но наилучшим не являлся. При обработке большого количества длинных ДНК, нахождение более выгодных порядков обхода может принести выигрыш. В случае малых размерностей такой поиск неоправдан.

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


Список литературы

  1. National Center for Biotechnology Information: nlm.nih.gov/.
  2. Смит Б. Методы и алгоритмы вычислений на строках. М.: Вильямс, 2006.
  3. Томский государственный университет: u/.
  4. TOP500 List – June 2007 (101-200): ссылка скрыта
  5. Moore, Gordon E. Cramming more components onto integrated circuit // Electronics Magazine, 1965.




ISBN 978-5-7262-0883-1. НАУЧНАЯ СЕССИЯ МИФИ-2008. Том 11