МУМмер
MUMmer — это биоинформационная программная система для выравнивания последовательностей . Он основан на структуре данных суффиксного дерева . Он использовался для сравнения различных сборок геномов друг с другом, что позволяет ученым определить, как изменился геном. Аббревиатура «МУМмер» происходит от «Максимальных уникальных совпадений» или MUM.
Оригинальные алгоритмы программного пакета MUMMER были разработаны Артом Делчером, Саймоном Касифом и Стивеном Зальцбергом. Mummer была первой системой сравнения всего генома, разработанной в биоинформатике. Первоначально он применялся для сравнения двух родственных штаммов бактерий.
Программное обеспечение MUMmer имеет открытый исходный код . Систему поддерживают главным образом Стивен Зальцберг и Артур Делчер в Центре вычислительной биологии Университета Джонса Хопкинса .
MUMmer — это широко цитируемая биоинформационная система в научной литературе. По данным Google Scholar, по состоянию на начало 2013 г. оригинальная статья MUMmer (Delcher et al., 1999) [1] цитировался 691 раз; статья MUMmer 2 (Delcher et al., 2002) [2] цитировался 455 раз; и статья MUMmer 3.0 (Курц и др., 2004). [3] цитировалось 903 раза.
Обзор
[ редактировать ]Mummer — это быстрый алгоритм, используемый для быстрого выравнивания целых геномов. Алгоритм MUMmer относительно новый и имеет 4 версии.
Версии МУМмеров
[ редактировать ]МУМмер1
[ редактировать ]MUMmer1 или просто MUMmer состоит из трех частей: первая часть состоит из создания суффиксных деревьев (для получения MUM), вторая часть - из самой длинной возрастающей подпоследовательности или самых длинных общих подпоследовательностей (для упорядочивания MUM), и, наконец, любого выравнивания для закрытия пробелов.
Перерывы между выравниванием MUM известны как пробелы. Другие алгоритмы выравнивания заполняют эти пробелы. Пробелы делятся на следующие четыре класса: [4]
- Прерывание SNP . – при сравнении двух последовательностей один символ будет отличаться
- Вставка – при сравнении двух последовательностей подпоследовательность появляется только в одной из последовательностей. Это был бы пустой пробел в другой последовательности в момент сравнения двух последовательностей.
- Высокополиморфная область – при сравнении двух последовательностей можно найти подпоследовательность, в которой каждый символ отличается.
- Повтор – это повторение последовательности. Поскольку MUM могут принимать только уникальные последовательности, этот пробел может представлять собой одно повторение одного из MUM.
МЮМмер 2
[ редактировать ]Этот алгоритм был переработан, чтобы требовать меньше памяти и увеличить скорость и точность. Это также позволяет добиться большего выравнивания геномов.
Улучшением стало количество, хранящееся в суффиксных деревьях за счет использования того, которое создал Курц.
МУМмер 3
[ редактировать ]По словам Стефана Курца и его товарищей по команде, «наиболее значительным техническим улучшением в MUMmer 3.0 является полное переписывание кода суффиксного дерева, основанное на компактном представлении суффиксного дерева». [5] дерево, описанное в статье «Уменьшение занимаемого места суффиксными деревьями». [6]
МУММЕР 4
[ редактировать ]По словам Гийома и его команды, в реализации есть некоторые дополнительные улучшения, а также инновации в параллелизме запросов. «Теперь в MUMmer4 есть опции для сохранения и загрузки массива суффиксов для данной ссылки». [7] Это позволяет построить суффиксное дерево один раз и построить его снова после запуска из сохраненного суффиксного дерева.
Программное обеспечение – открытый исходный код
[ редактировать ]MUMmer имеет программное обеспечение с открытым исходным кодом , и к нему можно получить доступ в Интернете.
Связанные выравнивания последовательностей
[ редактировать ]Существуют и другие типы выравнивания последовательностей:
- Изменить расстояние
- ВЗРЫВ
- Галстук-бабочка
- Миссис
- Блат
- Лиловый
- ЛАСТЗ
- ВЗРЫВ
Ссылки
[ редактировать ]- ^ Делчер, Алабама; Касиф, С.; Флейшманн, РД; Петерсон, Дж.; Уайт, О.; Зальцберг, СЛ (1999). «Выравнивание целых геномов» . Исследования нуклеиновых кислот . 27 (11): 2369–2376. дои : 10.1093/нар/27.11.2369 . ПМК 148804 . ПМИД 10325427 .
- ^ Делчер, Алабама; Филиппи, А.; Карлтон, Дж.; Зальцберг, СЛ (2002). «Быстрые алгоритмы крупномасштабного выравнивания и сравнения геномов» . Исследования нуклеиновых кислот . 30 (11): 2478–2483. дои : 10.1093/нар/30.11.2478 . ПМЦ 117189 . ПМИД 12034836 .
- ^ Делчер, А.; Хармон, Д.; Касиф, С.; Уайт, О.; Зальцберг, С. (1999). «Улучшенная идентификация микробных генов с помощью GLIMMER» . Исследования нуклеиновых кислот . 27 (23): 4636–4641. дои : 10.1093/нар/27.23.4636 . ПМК 148753 . ПМИД 10556321 .
- ^ Делчер, А.; Касиф, С.; Флейшманн, Р.; Петерсон, Дж.; Уайт, О.; Зальцберг, С. (1999). «Выравнивание целых геномов» . Исследования нуклеиновых кислот . 27 (11): 2369–2376. дои : 10.1093/нар/27.23.4636 . ПМК 148804 . ПМИД 10325427 .
- ^ Курц, С.; Филиппи, А.; Делчер, А.; Смут, М.; Шамуэй, М.; Антонеску, К.; Зальцберг, С. (2004). «Универсальное и открытое программное обеспечение для сравнения больших геномов» (PDF) . Геномная биология . 5 (2): Р12. дои : 10.1186/gb-2004-5-2-r12 . ПМК 395750 . ПМИД 14759262 . Архивировано (PDF) из оригинала 11 июля 2019 г. Проверено 06 мая 2021 г.
- ^ Курц, С. (1999). «Уменьшение требований к пространству для суффиксных деревьев» . Программное обеспечение: практика и опыт . 29 (13): 1149–1171. doi : 10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O . Архивировано из оригинала 06 мая 2021 г. Проверено 06 мая 2021 г.
- ^ Марсе, Гийом.; Пиллиппи, А.; Делчер, А.; Костон, Р.; Зальцберг, С.; Зимин, А. (2018). «MUMmer4: Быстрая и универсальная система выравнивания генома» . PLOS Вычислительная биология . 14 (1): e1005944. Бибкод : 2018PLSCB..14E5944M . дои : 10.1371/journal.pcbi.1005944 . ПМК 5802927 . ПМИД 29373581 .