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


 

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

29575. Использование особенностей электронных средств массовой информации в процессе формирования общественного мнения 12.23 KB
  Приемы аудиовизуальных СМИ для воздействия на мнение публики: использование ч б – цветного видео в программе; композиционные спецэффекты; настойчивая ежедневная трансляция мифообразов и ключевых фраз; избирательный монтаж; специальный хронометраж эфира; использование имиджа СМИ и отдельных журналистов. Прием дробление и мозаичность сообщений знания складываются из разрозненных обрывков информации. Мозаичность создает смысловой шум затрудняющий ориентацию в информационном потоке Прием сенсационность Быстро чередующиеся...
29576. Реклама как вид массовой коммуникации. Функции и стадии рекламной коммуникации 15.38 KB
  Функции и стадии рекламной коммуникации. Основными функциями социальной коммуникации являются:1 информационная передача информации;2 экспрессивная способность выражать не только смысловую но и оценочную информацию;3 прагматическая способность передавать коммуникационную установку предписывающую определенное воздействие на получателя.Как видно рекламе как коммуникации свойственно выполнение всех трех указанных функций.
29577. Коммерческая и социальная реклама в СМК 15.24 KB
  Функции выполняемые социальной и коммерческой рекламы посредством СМК: 1. Коммерческая реклама: В соответствие с современным подходом к изучению рекламы коммерческая реклама входит в комплекс маркетинговых коммуникаций в который помимо рекламы входят такие инструменты как стимулирование сбыта PR пропаганда и личные продажи. Социальная реклама вид некоммерческой рекламы направленной на изменение моделей общественного поведения и привлечения внимания к проблемам социума. В 1993 году был образован негосударственный Рекламный Совет в...
29578. Состояние медиарынка в кризисный и поскризисный период, тенденции дальнейшего развития 24.52 KB
  Те компании которые выжили в это время оказались в очень неплохой ситуации. Как отмечают специалисты основным принципом коммуникаций в кризисной ситуации – не замалчивать события говорить все и как можно скорее. Однако на ранних стадиях кризисной ситуации не следует говорить вещей которых вы не знаете или в которых вы не уверены не следует включаться в догадки поскольку вы можете оказаться не правы. Американские специалисты предлагают учитывать следующие позиции в подобной ситуации [10 с.
29579. Телевидение XXI века: соотношение социальных, политических и коммерческих функций 13.23 KB
  Степень этой вовлеченности и мера воздействия ТВ на аудиторию в плоскости выполнения этой функции зависят от той системы в которой действует данное телевизионное СМИ. Особенно сильно подобное отношение к СМИ вообще и к ТВ в частности у населения постсоветских государств. Люди ждут реакции властей на критические выступления касающиеся тех или иных явлений жизни по инерции доставшейся от советской системы в то время как СМИ – лишь способ донести информацию об этих явлениях до своей аудитории. Дальнейшее зависит уже не от СМИ выпадающего из...
29580. Интернет: история, возможности и прогнозы 16.93 KB
  Интернет: история возможности и прогнозы. Исторически интернет произошел от американской сети RPNET которая разрабатывалась как децентрализованное средство обмена информацией в случае ядерного удара. Прототип интернета RPNET в 1969 соединил сеть американских научно исследовательских университетов. Следующим значительным скачком в развитии интернета стал концепт всемирной паутины выдвинутый в 1989 Тимом БернсЛи идея создания универсального языка HTML Аштэмэйли протокола связи HTTPАштэтэпэ что позволило сделать интернет таким каким он...
29581. Информационное общество: основные характеристики, тенденции развития. Дискуссии в отношении позитивных изменений и негативных последствий всеобщей информатизации и глобализации мирового пространства 16.15 KB
  Информационное общество – ступень в развитии современной цивилизации характеризующаяся увеличением роли информации и знаний в жизни общества; возрастанием доли инфокоммуникаций информационных продуктов и информационных услуг в валовом внутреннем продукте ВВП; созданием глобального информационного пространства обеспечивающего эффективное информационное взаимодействие людей их доступ к мировым информационным ресурсам и удовлетворение их социальных и личностных потребностей в информационных продуктах и услугах. Основные характеристики:...
29582. Массовое сознание 12.93 KB
  На общественное мнение влияют мнения людей признаваемых обществом авторитетными и компетентными личный опыт людей В формировании общественного мнения выделяются: субъект воздействия – элитные группы стремящиеся к достижению или удержанию власти заказчики и исполнители государство аналитики журналисты и т.; объект воздействия – массовое сознание изменение которого является целью субъекта; инструмент воздействия – СМИ как массмедиа так и институты социализации культура и т. Формы и способы влияния общественного мнения на личность...
29583. Массовое сознание: Субъективистский и объективистский подходы 14.37 KB
  Массовое сознание включает в себя понятие массы: МассаОртега и Гаса это суждение некомпетентных низкое качество современной цивилизации; Масса Юнгер механизное общество в котором человек является придатком машины; Масса Зиммель Вебер Манхейм – это бюрократическое общество которое отличается широко расчленненой организацией в которой принятие решений допускается на высших этапах иерархии; МассаЛенин – совокупность трудящихся наименее организованных и просвещенных. МассаШарков это шаблонное Например когда в деревнях все...