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


 

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

76535. Закономерности усвоения родного языка и вытекающие из них принципы 34.5 KB
  Способность ребенка понимать отвлеченное лексическое значение слова в дальнейшем приводит его к пониманию слова как части речи. В какие сроки ребенокдошкольник овладевает указанными выше фактами языка и овладевает ли зависит от того как его обучают речи каков развивающий потенциал языковой среды в которой он растет а самое главное имеет ли он возможность усваивать грамматические и лексические значения родного языка синхронно в нужных пропорциях. Письменная речь усваивается если ее опережает развитие устной речи если она является как...
76536. Упражнения по русскому языку и их виды 27.5 KB
  Приступа по критериям: Упражнение зависит от характера мыслительной деятельности учащихся аналитической и тдОт времени выполненияОт последовательности связано с этом усвоения языкового материала: 1. Пропедовтическиеподготовка к восприятию нового материала ок цент на изучаемую единицу;Иллюстративные наиболее ярко показать примеры тех языковых фактов которые разбираются на уроке;Закрепительные закрепление теоретических сведения: постоянно воспроизведение существенных признаков изучаемого материала.
76537. Методы и приемы обучения русскому языку 40 KB
  Метод - способы взаимодействия учителя и ученика, направленные на достижение положительных результатов обучения. Положительные результаты - достижение цели. Действия: учение и обучение. Классификация Дубникова (основа: характеристика способов мышления - индукция(от частного к общему) и дедукция)
76538. Диктант как метод обучения и форма контроля 32 KB
  Диктант как метод обучения и форма контроля. Среди упражнений с помощью которых происходит формирование умений и навыков используется списывание простое и осложненное обучающие диктанты а также упражнения творческого характера: конструирование словосочетаний и предложений изложения и сочинения малых форм; разные виды грамматического разбора. В методике разработаны различные виды обучающих диктантов. Диктант с карточками удобен на первых этапах закрепления: дети записывают слова поднимая карточку с изучаемой орфограммой что позволяет...
76539. Теоретические методы усвоения русского языка 26.5 KB
  Теоретические методы усвоения русского языка. Федоренко выделяет методы практического изучения языка объяснение непонятных слов подготовка устных сообщений письменных сочинений составление планов конспектов тезисов исправление ошибок грамматических и стилистических обучение работе со справочной литературой методы теоретического изучения языка беседа сообщение чтение правил в учебнике методы теоретикопрактического изучения языка различные упражнения: при изучении грамматики грамматический разбор анализ готового материала...
76540. Языковой разбор и его роль в формировании знаний, навыков и умений обучающихся 30 KB
  Языковой разбор и его роль в формировании знаний навыков и умений обучающихся. Языковый разбор представляет собою лингвистический анализ и толкование предложенного учителем дидактического материала: это могут быть отдельные слова предложения небольшие тексты. Языковый разбор основывается на рецептивной деятельности учащихся так как проводится на готовом языковом материале восприятие которого сквозь призму изученных понятий и правил и составляет суть метода. В зависимости от того какое умение отрабатывается различаются следующие виды...
76542. Методы практического изучения языка и обучения речи. Анализ текста на уроке русского языка 26.5 KB
  Анализ текста на уроке русского языка. Сочинение вид письменной школьной работы изложение своих мыслей знаний на заданную тему Анализ текста. анализ текста создаёт условия для формирования у школьников представления о языковой системе реализации внутрипредметных межуровневых а также метапредметных связей включает уроки русского языка в единую систему филологического образования. Определить тему и проблему текста 3.
76543. Урок как основная форма обучения. Основные свойства и структура урока 32.5 KB
  Урок как основная форма обучения. Основные свойства и структура урока. Классификация: урок объяснение новых знаний введение новых теоретических понятий уроки закрепления формирования умений и навыков урок повторения и обобщения урок контролирования или контрольный урок. комбинированный урок классический Классификация в соответствии с ведущим методом обучения: урок лекция урок семинар урок практикум урок зачетТак же выделяются уроки развития речи2 направления: развитие речи на уроке с любой темой то есть изучение грамматики и...