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


 

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

65288. Експериментальне дослідження просторово-часових характеристик завад від морської поверхні й неоднорідностей тропосфери для оптимізації пристроїв обробки сигналів радіотехнічних систем 982 KB
  Проблема забезпечення безпечного судноводіння в умовах обмеженої видимості й у складних метеоумовах належить до однієї з найбільш затребуваних завдань сучасної навігації. При цьому використанню радіолокаційних засобів немає альтернатив, тому що виявлення...
65289. Швидкий пошук різноформатних даних в граничних режимах систем управління 845 KB
  Сучасний розвиток промисловості характеризується зростанням вимог до інформаційного забезпечення інтеґрованого організаційно-адміністративного управління на верхньому рівні ієрархії та жорсткими вимогами...
65290. Творчість Палладія Еленопольського в контексті формування ідеалів християнського життя: історико-соціальний аспект 208.5 KB
  Актуальність роботи зумовлюється і тим що дослідження процесу використання біблійних текстів у конструюванні християнського дискурсу за часів Пізньої Античності є відносно новими і нечастими; ця сфера історичних досліджень лише нині почала активно розвиватися в зарубіжній історіографії...
65291. ФОРМУВАННЯ ФАХОВОЇ КОМПЕТЕНТНОСТІ МАЙБУТНІХ ІНЖЕНЕРІВ-МЕТАЛУРГІВ У ПРОЦЕСІ ВИВЧЕННЯ ПРОФЕСІЙНО ОРІЄНТОВАНИХ ДИСЦИПЛІН 217 KB
  Необхідність підвищення рівня фахової компетентності майбутніх інженерівметалургів зумовлена інтенсивною модернізацією вітчизняного металургійного...
65292. Формування дослідницьких умінь студентів технічних університетів у процесі вивчення професійно-орієнтованих дисциплін 538.5 KB
  Критерії: 1 мотиваційно-ціннісний 2 когнітивний 3 діяльнісний формування ціннісного ставлення до дослідницької діяльності; створення в технічному університеті професійнодослідницького середовища; забезпечення...
65293. Підвищення ефективності процесу електродугового наплавлення шляхом використання комбінованих магнітних полів 2.57 MB
  Встановлення особливостей впливу КМП на процеси утворення форми посилення валика та форми проплавлення основного металу при дуговому наплавленні під флюсом дасть можливість розробити рекомендації для вибору оптимальних параметрів...
65294. ФОРМУВАННЯ ЗАГАЛЬНОТЕХНІЧНИХ ЗНАНЬ У ПРОЦЕСІ ПРОФЕСІЙНОЇ ПІДГОТОВКИ МАЙБУТНІХ УЧИТЕЛІВ ТЕХНОЛОГІЙ 221.5 KB
  Нерозробленість даної проблеми наявні протиріччя обумовили вибір теми дисертаційного дослідження: Формування загальнотехнічних знань у процесі професійної підготовки майбутніх учителів технологій.
65295. СУЇЦИДАЛЬНИЙ ДИСКУРС В УКРАЇНСЬКІЙ ПРОЗІ 20-30-Х РР. ХХ СТ. (ПСИХОАНАЛІТИЧНА ІНТЕРПРЕТАЦІЯ) 165.5 KB
  Актуальність дослідження зумовлюється подальшим розвитком психоаналітичної інтерпретації в сучасному українському літературознавстві, що передбачає освоєння нової проблематики, якою є наразі суїцидальна образність.
65296. ТУРБІННИЙ ВИМІРЮВАЛЬНИЙ ПЕРЕТВОРЮВАЧ ВИТРАТ З ГІДРОДИНАМІЧНИМ ВРІВНОВАЖЕННЯМ ЧУТЛИВОГО ЕЛЕМЕНТА 5.41 MB
  Для визначення кількісних показників потоків широкого застосування набули прилади та системи вимірювання витрат рідин з турбінними перетворювачами витрат ТПВ завдяки їх перевагам перед існуючими приладами інших класів аналогічного призначення.