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


 

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

31886. Кассир. Должностные обязанности 23 KB
  Должен знать: постановления распоряжения приказы другие руководящие и нормативные документы вышестоящих и других органов касающиеся ведения кассовых операций; формы кассовых и банковских документов; правила приема выдачи учета и хранения денежных средств и ценных бумаг; порядок оформления приходных и расходных документов; лимиты остатков кассовой наличности установленной для организации; правила обеспечения их сохранности; порядок ведения кассовой книги составления кассовой отчетности; правила эксплуатации электронно вычислительной...
31887. Работа с формулами. Абсолютная и относительная адресация при работе с формулами 44.5 KB
  Вам необходимо определить стоимость каждой квартиры таким образом чтобы общая сумма полученных денег равнялась 7 млн. Известно что: дом 6ти этажный кирпичный; на каждом этаже по 4 квартиры 1но 2х 3х и 4х комнатные общей площадью 63; 90; 118; 146 соответственно; стоимость квартир зависит от этажа на первом и последнем дешевле; стоимость 1 м2 в центре Екатеринбурга 60. В ячейку G2 введите стоимость одного квадратного метра 60. Выделите все ячейки связанные с суммами стоимость квартир и задайте Финансовый формат с двумя...
31888. Сердечно-легочная и церебральная реанимация 103 KB
  Проверить реакцию пострадавшего: аккуратно встряхнуть его за плечи и громко спросить Что с Вами€. Принять решение: если пострадавший реагирует оставить его в том же положении попытаться выяснить причины происходящего и позвать на помощь регулярно оценивать состояние пострадавшего; если пострадавший не реагирует громко позвать на помощь повернуть на спину и открыть дыхательные пути путем запрокидывания головы и подтягивания подбородка рукой нужно надавить на лоб а другой рукой подтянуть подбородок. Альтернативный способ ...
31889. Русский язык и культура речи 247 KB
  ФОНЕТИЧЕСКИЙ УРОВЕНЬ Содержит задания отражающие проблемы связанные с нормами постановки ударения акцентологические нормы. СЛОВООБРАЗОВАТЕЛЬНЫЙ УРОВЕНЬ В заданиях необходимо найти ошибки допущенные при образовании слов и исправить их. ГРАММАТИЧЕСКИЙ УРОВЕНЬ В данном блоке представлен комплекс заданий на проверку знания морфологических норм нормы образования форм слов различных частей речи и синтаксических норм нормы употребления форм слов в словосочетании и предложении нормы построения предложений. ЛЕКСИЧЕСКИЙ УРОВЕНЬ Данный блок...
31890. ПЛАНЫ СЕМИНАРСКИХ ЗАНЯТИЙ И ТЕМЫ РЕФЕРАТОВ ПО ФИЛОСОФИИ 377.5 KB
  Горького Рассмотрены на заседании кафедры философии Протокол № 7 от 4 апреля 2005 г. Творческое усвоение студентами философии т. При творческом усвоении философии у студентов формируются следующие умения по различным блокам философского знания: историкофилософский блок: вычленять смысл философской системы: как в ней решаются вопросы метафизики антропологии гносеологии аксиологии культурологии социологии политологии праксиологии; определять педагогическую значимость той или иной философской системы и аргументировать ответ;...
31891. Методические рекомендации, планы семинарских занятий и темы контрольных работ по философии 198.5 KB
  Андреев Одобрены на заседании кафедры философии. кафедрой философии С. 2005 Введение При усвоении дисциплины студент должен иметь программу по философии в которой отражены цели задачи требования к уровню усвоения содержания дисциплины приведена основная и дополнительная литература по всем темам курса контрольные вопросы для подготовки к экзамену.
31892. Задания и методические указания для выполнения курсовых работ по дисциплине «Основы маркетинга» 77.5 KB
  Шапошников Одобрена на заседании кафедры менеджмента и маркетинга. Методические указания к написанию курсовой работы Главное условие успешного овладения студентами знаниями в области дисциплины Основы маркетинга заключается в самостоятельной систематической работе. При высоком уровне знаний проявленных при защите курсовой работы и другим контрольным мероприятиям а также на практических занятиях по дисциплине Основы маркетинга студент может быть освобожден от экзамена.