4430
правок
Сортировка перестановок со знаками при помощи обращений (последовательность обращений): различия между версиями
Материал из WEGA
Сортировка перестановок со знаками при помощи обращений (последовательность обращений) (посмотреть исходный код)
Версия от 12:48, 26 февраля 2019
, 26 февраля 2019нет описания правки
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 72: | Строка 72: | ||
Обобщения этого подхода для сравнения более чем двух геномов широко рассматривались в литературе и применялись для реконструкции эволюционных событий и организации геномов общих предков биологических видов, а также для вывода ортологичных генов на основе их позиций; они основаны на эвристических принципах, базирующихся на теории сортировки подписанных перестановок при помощи обращений [12, 13]. | Обобщения этого подхода для сравнения более чем двух геномов широко рассматривались в литературе и применялись для реконструкции эволюционных событий и организации геномов общих предков биологических видов, а также для вывода ортологичных генов на основе их позиций; они основаны на эвристических принципах, базирующихся на теории сортировки подписанных перестановок при помощи обращений [12, 13]. | ||
== Открытые вопросы == | |||
• Уменьшение сложности ниже значения <math>O(n^{3/2})</math>. Этого можно добиться за счет применения более рациональной структуры данных или изменения принципа работы алгоритма, в силу чего отпадет необходимость применения на каждом этапе обращения сортировки для получения возможности вычисления следующих. | |||
• Эффективное представление и перечисление всего множества решений (определенные шаги в этом направлении были сделаны в работах [3, 6]). | |||
• Поиск среди всех решений таких, которые удовлетворяли бы некоторым биологическим ограничениям – таким как сохранение некоторой общей группы генов или приоритетность небольших инверсий (некоторые достижения представлены в работе [7]). | |||
== Экспериментальные результаты == | |||
Алгоритм Танье, Бержерон и Сагот [18] был реализован в его квадратичной версии (без конкретной структуры данных, что, вероятно, имеет смысл только для перестановок очень большого размера) Дикманном (http://biomserv.univ-lyon1.fr/~tannier/PSbR/), однако не сообщалось ни о реализации структур данных, ни об экспериментальных данных по сложности. | |||
== Ссылки на код == | == Ссылки на код == | ||
| Строка 93: | Строка 103: | ||
Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки подписанных перестановок при помощи обращений, а также для выдачи сжатого представления всех оптимальных последовательностей перестановок, является реализацией алгоритма из работы [6]. | Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки подписанных перестановок при помощи обращений, а также для выдачи сжатого представления всех оптимальных последовательностей перестановок, является реализацией алгоритма из работы [6]. | ||
== См. также == | == См. также == | ||
