Войти
MUMmer - это программная система биоинформатики для выравнивания последовательностей. Он основан на структуре данных дерева суффиксов и является одной из самых быстрых и эффективных систем, доступных для этой задачи, что позволяет применять ее к очень длинным последовательностям. Он широко используется для сравнения разных геномов друг с другом. В последние годы он стал популярным алгоритмом сравнения геномных сборок друг с другом, который позволяет ученым определять, как геном изменился после добавления дополнительных последовательностей ДНК или после запуска другой программы сборки генома. Аббревиатура «MUMmer» происходит от «Максимальные уникальные совпадения» или MUM. Оригинальные алгоритмы в программном пакете MUMMER были разработаны Артом Делчером, Саймоном Касифом и Стивеном Зальцбергом. Mummer был первой системой сравнения полных геномов, разработанной в биоинформатике. Первоначально он применялся для сравнения двух родственных штаммов бактерий.
Программное обеспечение MUMmer имеет открытый исходный код, и его можно найти на домашней странице MUMmer. На домашней странице также есть ссылки на технические документы с описанием системы. Система поддерживается в первую очередь Стивен Salzberg и Артур Delcher в Центре вычислительной биологии в Университете Джона Хопкинса.
MUMmer - это система биоинформатики, которую часто цитируют в научной литературе. Согласно Google Scholar, по состоянию на начало 2013 года исходная статья MUMmer (Delcher et al., 1999) была процитирована 691 раз; статью MUMmer 2 (Delcher et al., 2002) цитировали 455 раз; а статью MUMmer 3.0 (Kurtz et al., 2004) цитировали 903 раза.
Вы задаетесь вопросом, какое у вас отношение к обезьяне? Если ответ положительный, я могу сказать вам, что есть алгоритмы, в которых вы можете найти этот ответ. Если бы у вас были классы алгоритмов, на ум могли бы прийти «Редактировать расстояние» (Вунча и Нидлмана); который можно использовать для этой же темы. Однако для сравнения небольших последовательностей используется алгоритм «Расстояние редактирования», поэтому вычисление выравнивания генома займет много времени.
Геномы - это большая последовательность генетических инструкций / информации об организме (в хромосоме); теперь представьте, что «сравнивая последовательность размером 4 Мбайт, такую как M. Tuberculosis, с другой последовательностью 4 Мбайт, многим алгоритмам либо не хватает памяти, либо требуется слишком много времени для выполнения» (Arthur et al., 1999). В то время 4 Мб памяти было огромным делом; так что они должны были что-то делать с этим, например, создавать алгоритмы такого типа. Исследователи создают алгоритмы для сравнения последовательностей геномов. Mummer - это быстрый алгоритм, который в основном используется для быстрого выравнивания целых геномов.
MUMmer, как упоминалось ранее, представляет собой систему / процесс для эффективного выравнивания последовательностей большого размера, этот алгоритм использовался для открытия структуры генома. Алгоритм действительно хорошо разработан, и он способен сравнивать выравнивания за секунды. Поскольку этот алгоритм относительно новый, у него есть четыре версии, одна лучше, чем предыдущая.
MUMmer1 или просто MUMmer состоит из трех частей: первая часть состоит из создания деревьев суффиксов (для получения MUM), вторая часть в самой длинной возрастающей подпоследовательности или самых длинных общих подпоследовательностях (чтобы упорядочить MUM), наконец, любое выравнивание для закрытия пробелов.
Напоминаем, что для запуска процесса нам нужно получить в качестве входных данных два генома. Как только мы их получим, мы будем искать максимальное количество уникальных совпадений ( MUM ). Алгоритм MUMs имеет свою логику, поскольку это можно сделать несколькими способами. Например, наивный алгоритм просматривает все последовательности из одного генома и сравнивает его с другими последовательностями, что требует O (m * m2), где m и m2 являются двумя геномами. Однако, поскольку MUMmer должен быть быстрым, он использует структуру данных, называемую суффиксным деревом ( Suffix tree ), которое занимает O (m + m2). Из этого дерева мы извлекаем MUM (которые представляют собой подпоследовательности, представленные одним внутренним узлом обеими последовательностями).
Как только мы идентифицируем MUM, нам нужно выбрать геном и отсортировать (и, возможно, удалить) MUM на основе положения другого генома. Этот шаг можно легко выполнить, выбрав геном и перечислив узлы (MUM) в порядке возрастания, а на втором шаге мы перечислим каждый узел в соответствии с узлом из первой последовательности. Другими словами, мы перечисляем пару MUM (с точным совпадением из обоих геномов) с одним и тем же значением независимо от положения. Потом сортируем. Для этого мы можем выбрать любой из доступных методов. Например, это можно сделать с помощью длинной общей подпоследовательности (проблема самой длинной общей подпоследовательности ) или длинной возрастающей подпоследовательности ( LIS ). В конце этого процесса MUM в обеих последовательностях выравниваются / упорядочиваются одинаково (некоторые MUM пока игнорируются, поскольку мы не можем иметь значение, пронумерованное большим числом, перед значением, пронумерованным небольшим числом). Лучшая временная сложность для этого шага - O (nlogn).
Наконец, мы должны иметь дело с перерывами между MUM-выравниванием, которые могут быть известны как пробелы. Мы используем другие алгоритмы выравнивания, которые могут заполнить эти пробелы. Артур и его команда (Arthur et al., 1999) отмечают, что пробелы делятся на следующие четыре класса:
Этот алгоритм был переработан, чтобы требовать меньше памяти, процесс выполняется быстрее и точнее, чем первый; Это также позволяет выравнивать большие геномы.
Улучшение заключалось в количестве, сохраненном в деревьях суффиксов, благодаря использованию созданного Курцем. Для этого дерева вставка отличается, так как это просто плагин только одной последовательности, другой - для сравнения (это похоже на добавление, но это не так, мы сравниваем символы в дереве). Это уменьшает сложность пространства, поскольку хранит одну последовательность.
Наконец, первый алгоритм MUMmer только выровнял две последовательности и перешел к другому шагу. Однако для достижения лучшего охвата последовательности MUM становятся кластерами (что означает, что это группа сообщений MUM, разделенных меньшим количеством пробелов).
По словам Стефана Курца и его товарищей по команде, «наиболее значительным техническим усовершенствованием в MUMmer 3.0 является полное переписывание кода дерева суффиксов на основе компактного представления дерева суффиксов» дерева, описанного в статье «Уменьшение потребности в пространстве. суффиксных деревьев ».
Еще одним улучшением было расслабление МАМ. Это означает, что теперь у пользователя есть возможность найти все неуникальные максимальные совпадения, все совпадения, которые уникальны только в выбранной последовательности, или исходные MUM (которые уникальны для обеих последовательностей). Это было добавлено, чтобы избежать каких-либо пропущенных подпоследовательностей, которые были копиями MUM.
По словам Гийома и его команды, есть некоторые дополнительные улучшения в реализации, а также инновации с параллелизмом запросов. Первое и самое большое улучшение - это увеличение предельного размера для тестируемой последовательности. Наконец, «MUMmer4 теперь включает опции для сохранения и загрузки массива суффиксов для данной ссылки» (Marcais et al., 2018). Благодаря этому суффиксное дерево может быть построено один раз и построено снова после его запуска из сохраненного суффиксного дерева.
MUMmer имеет программное обеспечение с открытым исходным кодом. Лучший способ начать играть с этим пакетом - перейти на его веб-сайт, указанный ниже.
На этой странице рассказывается об открытом исходном коде, требованиях и этапах установки, процессе запуска пакета и некоторых примерах выполняемых последовательностей. На этом сайте есть дополнительная информация. Если вы застряли, на сайте есть информация о том, к кому обращаться в таких случаях. Эта страница содержит ценную информацию для работы с этим алгоритмом.
Существуют и другие типы выравнивания последовательностей, некоторые из связанных тем показаны ниже:
