77229

Параллельная реализация алгоритма ACO

Курсовая

Информатика, кибернетика и программирование

В настоящее время биоинформатика также включает в себя теоретические методы и алгоритмы решения задач возникающих из анализа биологических данных.

Русский

2015-02-02

69 KB

1 чел.

Санкт-Петербургский Государственный Университет

Математико-механический факультет

Кафедра системного программирования


Параллельная реализация алгоритма ACO

Курсовая работа студентки 444 группы
Дырдиной Анны Викторовны

Научный руководитель

Аспирант кафедры

Системного Программирования

Вахитов А. Т.

Санкт-Петербург

2009


Введение

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

Анализ последовательности генов

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

Метод сопоставления последовательностей.

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

Ant Colony Optimization Algorithm (ACO)

Ant Colony Optimization Algorithm – вероятностный алгоритм решения вычислительных задач, которые могут быть сведены к поиску оптимальных путей в графе. Он основан на реальном поведении муравьев. Изначально муравьи не знакомы с территорией вокруг муравейника. Они ползут в произвольном направлении в поисках еды или стройматериалов, оставляя на пути запах феромонов. С течением времени феромоны испаряются. Чем короче маршрут, и чем чаще муравей успевает по нему проползти, тем сильнее запах феромонов. Таким образом, через какое-то время муравьи используют только кратчайшие пути к еде. При поиске оптимального пути в графе «лучший» путь имеет наибольший вес – аналог феромона в природе.

 Теоретическая часть

Сценарии перестановки геномов

Геномы современных видов были сформированы множеством эволюционных механизмов, одним из которых является перестановка геномов. Гипотеза о том, что между наследственным и текущим геномом могли быть перестановки, обеспечивает понимание механизмов молекулярного развития. Вычисление минимального количества перестановок между геномами – расстояние между ними – хорошо изученная биоинформатическая задача. Показать последовательность шагов, соответствующих расстоянию между геномами, - связанный вопрос. Алгоритм нахождения этой последовательности – алгоритм нахождения оптимального сценария. Существуют достаточно быстрые алгоритмы нахождения единственного сценария между геномами, тогда как на самом деле их гораздо больше. Поэтому встает задача о нахождении набора сценариев, которые были бы и оптимальными, и в то же время, правдоподобными с точки зрения биологии. Один из возможных подходов – сокращение  пространства поиска с помощью добавления биологических ограничений. Так же можно рассматривать только сценарии, сохраняющие общие части между геномами, или строить множества эквивалентных сценариев.

ACO алгоритм: основные термины

Для исследования пространства эволюционных сценариев можно использовать ACO метод. Этот метод позволяет исследовать оптимальный (кратчайший) сценарий, а также близкий к оптимальному. Он также позволяет задать метрику (количество феромонов) на исследованных сценариях, которая потом может использоваться для биологически правдивых сценариев.

Стандартный способ кодирования мультихромосомных геномов – подписанные перестановки геномных маркеров. Хромосома π = (π1,..πm) представляется последовательностью геномных маркеров. N-хромосомный геном Π определяется как множество хромосом {π_1,..π_n}. Маркеры принимают значение от 1 до n и могут встречаться в геноме только один раз, также хромосома π = (π1,..πm) и -π = (-πm,..-π1) эквивалентны.

Каноническая форма представления геномов: (1) первый маркер в каждой хромосоме по абсолютному значению меньше, чем последний, (2) хромосомы сортируются по первому маркеру

Пример: геном Π имеет три хромосомы π_1 = (-3, 1, 5, 4), π_2 = (7, 6) и π_3 = (9, 2, -8). В канонической форме он выглядит так: π_1 = (-6, -7), π_2 = (-3, 1, 5, 4) и π_3 = (8, -2, -9).

Рассматривается стандартный набор перестановок применимых к геному: инверсия, слияние, транспозиция, деление.

Граф перестановок G=(V, E) – граф, каждая вершина которого – уникальный мультихромосомный геном. Дуги представляют геномные перестановки, то есть два генома Π и Γ смежны тогда и только тогда, если d(П, Г) = 1 (d – функция расстояний).

Опр. Последовательность S = (П0,..Пm) – сценарий между n-хромосомными геномами П и Г, такая что

  •  для любого i є [0, m] Пin-хромосомный геном,
  •  П0=П, Пm=Г,
  •  для любого i є [0, m-1], di, Пi+1)=1.

Тогда если m=d(П, Г), то S – оптимальный сценарий.

Последовательность S, такая что m = d(П, Г)+α и без циклов называется α-оптимальным сценарием.

Любой путь в графе G соответствует одному сценарию, и количество оптимальных сценариев между геномами П и Г соответствует количеству кратчайших путей между П и Г.

Хранение графа G целиком невозможно даже для маленьких n. С помощью АСО  алгоритма можно выбрать подмножество геномов и ребер, на которых можно рассматривать подходящие и достаточно разнообразные эволюционные сценарии.

ACO алгоритм: вычисление последовательностей перестановок

Имеются два генома П и Г. Необходимо найти оптимальные и α-оптимальные сценарии.

Изначально в граф G записываются только два генома: начальная вершина П (муравейник) и конечная вершина Г (источник пищи). Количество феромона хранится на ребре и обозначается te, где e – ребро. Для муравья, находящегося в данной вершине, количество феромона на исходящие ребрах рассматривается как вероятность выбора ребра для следующего хода.

Рассматривается S поколений муравьев с А муравьями в каждом поколении. В каждом поколении каждый муравей начинает из П и пытается достигнуть Г не зависимо от других муравьев. Каждый муравей строит свой путь Т=(е1,..еk) за k шагов. Когда все пути посчитаны, феромон добавляется у всех ребер, участвующих в каждом пути, чтобы поощрить следующее поколение муравьев к выбору определенных ребер. Количество феромона, которое муравей оставляет на ребре е вычисляется по формуле Δte = 1/(k-d+1), где d=d(П, Г). Для каждого ребра из Т te = te + Δte.

Наконец, моделируется процесс испарения феромонов с помощью коэффициента испарения ρ (0<= ρ <=1). Когда каждый путь в поколении закончен, значение феромона каждого ребра обновляется te = ρ * te. Так как граф G большой мы не рассматриваем все теоретически возможные ребра, а только те, которые уже записаны.

При завершении пути Т мы записываем каждое ребро е из Т такое, что te >= ε (ε – определено заранее), а также связные вершины. Чтобы размер графа оставался небольшим, мы удаляем из него ребра таки, что te < ε и вершины, не имеющие соседей (за исключением П и Г).

Алгоритм прекращает свою работу, когда количество поколений равно S. S определяется экспериментально, исходя из числа подходящих сценариев, которое надо найти.

На практике можно столкнуться со следующей проблемой. Изначально граф G очень большой и имеет множество циклов, поэтому путь муравья может быть бесконечным. Поэтому вводится 3 различных значения феромона: tg – для хорошего ребра, которое приближает муравья к Г, tn – для нейтрального ребра, tb – для плохого ребра. То есть для любых вершин v, u и ребра e, соединяющего их, феромон t может быть:

  •  tg, если d(u, Г)=d(v, Г)-1,
  •  tn, если d(u, Г)=d(v, Г),
  •  tb , если d(u, Г)=d(v, Г)+1.

Так же для каждой вершины эти значения нормализуются делением их на количество исходящих ребер соответствующего типа. Это сделано потому что, если у вершины много исходящих ребер, но только небольшое их количество – хорошие, то существует возможность выбора неправильного направления.

Влияние значения добавляемого феромона высоко, когда муравей впервые проходит по ребру или для редко посещаемых вершин. Для популярных областей графа это влияние гораздо ниже. Если tg=tn=tb, то это классическая ситуация, если же tg>0=tn=tb, то исследуются только оптимальные сценарии.

ACO алгоритм: вычислительная сложность

Сложность АСО алгоритма больше всего зависит от процесса выбора соседних вершин в графе. Для стандартного алгоритма все соседи данной вершины вычисляются за О(n³) (n – количество элементов в геноме): О(n²) - соседей и О(n) – вычисление феромона на каждом исходящем ребре. Весь граф состоит из О(n!) вершин.

Точность результата работы алгоритма напрямую зависит от количества поколений и количества муравьев в каждом поколении. Поскольку в геноме достаточно много элементов (~100), и запускается большое количество муравьев, последовательная программа, реализующая данный алгоритм, либо будет работать слишком продолжительное время, либо выдавать неточный результат.

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

 Реализация

Распараллеливание алгоритма

Описанный выше алгоритм можно распараллелить двумя способами:

  •  По процессам. Запускается одновременно множество (более 100) независимых муравьев, которые через определенные промежутки времени обращаются к сохраненному графу и читают или записывают новые вершины и ребра. При этом способе экономится память, но возникают громоздкие вычисления.
  •  По данным. Пока существует только предположение, что можно разбить граф на куски с примерно одинаковой плотностью (количеством вершин и ребер) и хранить их в различных местах для уменьшения нагрузки на сервер. При этом важно выбирать куски так, чтобы в среднем муравью не пришлось слишком часто пересекать границы кусков.

В работе будет рассматриваться первый способ.

В связи с тем, что в выбранном методе требуется большое количество вычислений, то полезно было бы применять Грид-технологию. Она позволяет получить доступ к дополнительным вычислительным ресурсам, благодаря чему задача будет решаться в более краткие сроки.

Общая схема метода

1. Инициализация графа. Загрузка двух вершин: начальной и конечной.

2. Запуск муравьев в цикле:

2.1. Чтение муравьем обновлений из базы данных.

2.2. Вычисление нового пути в графе.

2.3. Загрузка нового пути в базу данных.

3. Количество итераций цикла определяется числом поколений муравьев, которое задается изначально.

Рис.1. Общая схема метода.

Этапы реализации

1. База данных. В приложении используется база данных для хранения событий обновлений: инициализация (добавление двух геномов – начального и конечного), добавление нового пути муравья, испарение феромона.

База данных состоит из двух таблиц: events и histories. В первой хранятся метки событий, во вторую добавляются новые пути.

Рис. 2. Схема базы данных.

В таблице events атрибут event_id используется для нумерации событий, атрибут event_type (может принимать значения init, history или evaporation) определяет тип события. Каждый раз, когда event_type = history в таблицу histories добавляется новый путь. Для пути из k ребер будет k записей – по одной на каждое ребро. Node_from – вершина, из которой выходит ребро, node_to – вершина, в которую оно входит. Начальный и конечный геном хранятся как событие init и кладутся в таблицу histories следующим образом: node_from = anthill, node_to = food.

К базе существуют следующие запросы:

  •  прислать все изменения базы данных,
  •  добавить в histories новый путь.

2. Клиентское приложение состоит из 3х частей:

  •  Скачивание обновлений из базы данных. Пути сохраняются как HashMap<Integer, Integer[][][]>, где ключ – это event_id из таблицы histories, а значение – трехмерный массив, в котором первая размерность всегда равняется двум. В Integer[0][][] сохраняются значения из столбца node_from (из таблицы histories), а в Integer[1][][] – из столбца node_to.
  •  Запуск метода, реализующего ACO алгоритм (используется готовый метод).
  •  Отсылка результатов прохождения муравья в базу данных.

3. Протокол взаимодействия.

3.1 Клиентское приложение посылает запрос обновлений серверу.

3.2 Сервер скачивает обновления из базы данных.

3.3 Используя полученные обновления, муравей проходит путь от начальной вершины до конечной.

3.4 Клиентское приложение посылает в запросе новый путь серверу.

3.5 Сервер добавляет путь в базу данных.

Результаты

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

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

  1.  Ant Colony Optimization Algorithm

http://www.aco-metaheuristic.org/

  1.  Sequence Alignment

http://en.wikipedia.org/wiki/Sequence_alignment

  1.  N. Vyahhi, A. Goeffon, M. Nikolski and D. Sherman, Swarming Along the Evolutionary Branches Sheds Light on Genome Rearrangement Scenarios, accepted for publication in GECCO 2009


 

А также другие работы, которые могут Вас заинтересовать

34566. Влияние идей структурализма, постструктурализма и постмодернизма на развитие послевоенной французской литературы 19.27 KB
  Барт различает не письмо и текст литературное произведение которое было основой классики. Текст вторичен соткан из цитат и многозначен. В тексте принципиально важна интертекстуальность. Барт: каждый текст является интертекстомпредставляет собой новую ткань сотканную из старых цитат.
34567. Антиутопия, фантастика, фэнтези в английской и американской литературе 20 в. (Д. Оруэл, Р. Бредбери, К. Вонегут, Д. Толкиен и др.) 19.65 KB
  Романы антиутопистов во многом схожи: каждый автор говорит о потере нравственности и о бездуховности современного поколения каждый мир антиутопистов это лишь голые инстинкты и эмоциональная инженерия[3]. В современном виде сформировался в начале XX века. Произведения фэнтези чаще всего напоминают историкоприключенческий роман действие которого происходит в вымышленном мире близком к реальному Средневековью герои которого сталкиваются со сверхъестественными явлениями и существами. В отличие от научной фантастики фэнтези не стремится...
34568. Движение «рассерженных» в английской литературе. Пьеса Д. Осборна «Оглянись во гневе» 19.53 KB
  Так герой пьесы Джимми Портер в Оглянись во гневе осыпает проклятиями все и вся но не произносит ни одной конструктивной мысли и обнаруживает полнейшую беззащитность перед ненавистным и угрожающим ему миром который наступает на него со всех сторон и с которым он не в силах бороться. лишь Джимми Портер. С первых слов пьесы и до ее последних строк звучит непрерывный вопль Джимми. Джимми Портер выходец из рабочей среды но его связи с ней давно порваны.
34569. Анитиколониальная и политическая проблематика в английском романе 21.82 KB
  Английский журналист Фаулер от лица которого идёт рассказ и молодой американский дипломат Пайл связанные с самого начала романа далеко не простыми взаимоотношениями. Его антиподом был английский репортёр Фаулер усталый душевно опустошённый человек который воспринимает себя как репортёра задача которого давать одни факты. Человек потерявший идеалы и лишённый каких либо стремлений Фаулер пытается остаться сторонним наблюдателем той борьбы и злодеяний которые развёртываются на его глазах и ищет утешения от страдания в любви. Именно...
34570. Жанр романа-притчи в творчестве У. Голдинга 17.9 KB
  В 43 года опубликовал 1й роман Повелитель мух за кот. Повелитель мух вырастает из традиции робинзонады. страхов мальчиков становится повелитель мух кабаний череп и эти страхи использует предводитель охотников Джек устанавливая на острове дикт. Повелитель мух написан как рн предупреждение.
34571. ПРИНЯТИЕ ХРИСТИАНСТВА НА РУСИ 17.8 KB
  ПРИНЯТИЕ ХРИСТИАНСТВА НА РУСИ Составитель: Ю. Подобная аргументация практически не нуждается в анализе реальных земных причин крещения Руси. Эти отношения обусловили лучший результат византийских миссионеров сумевших подготовить для православия на Руси более богатую почву. На Руси латынь была неизвестна а греческий язык был знаком многим купцам и части феодальной верхушки что также предопределило выбор веры Владимира.
34572. РУССКИЕ ЗЕМЛИ В ПЕРИОД ФЕОДАЛЬНОЙ РАЗДРОБЛЕННОСТИ (конец XI – XII вв.) 19.67 KB
  РУССКИЕ ЗЕМЛИ В ПЕРИОД ФЕОДАЛЬНОЙ РАЗДРОБЛЕННОСТИ конец XI XII вв. Русь вступает в период феодальной раздробленности. Тенденция к феодальной раздробленности проявилась еще в XI в. но условно принято считать началом раздробленности Киевской Руси смерть князя Мстислава Владимировича в 1132 г.
34573. ФОРМИРОВАНИЕ РУССКОГО ЦЕНТРАЛИЗОВАННОГО ГОСУДАРСТВА: ЭТАПЫ, ОСОБЕННОСТИ 19.82 KB
  ФОРМИРОВАНИЕ РУССКОГО ЦЕНТРАЛИЗОВАННОГО ГОСУДАРСТВА: ЭТАПЫ ОСОБЕННОСТИ Политическое объединение русских земель было драматичным и длительным процессом проходившим на протяжении более двух веков. Торговые связи московских купцов суконников и сурожан протянулись далеко за пределы русских земель. удалось увеличить территорию своего княжества почти вдвое захват Коломны присоединение Можайска и Переяславльских земель. Хан Узбек передал Калите право сбора дани со всех русских земель и доставки ее в Орду что привело к ликвидации системы...
34574. СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ И ПОЛИТИЧЕСКИЙ СТРОЙ РОССИЙСКОГО ЕДИНОГО ГОСУДАРСТВА (вторая половина XV – середина XVI вв.) 20.36 KB
  СОЦИАЛЬНОЭКОНОМИЧЕСКИЙ И ПОЛИТИЧЕСКИЙ СТРОЙ РОССИЙСКОГО ЕДИНОГО ГОСУДАРСТВА вторая половина XV середина XVI вв. Основную массу жителей Московского государства составляли крестьяне. Лошадь использовалась в поле и на различных отработках в пользу государства и феодала. В условиях аграрного строя крестьянский двор являлся главной единицей обложения налогами платежами оброками и повинностями со стороны государства владельцев вотчин и поместий.