Введение
Максимальное уникальное совпадение или MUM, сокращенно, является частью ключевого шага в выравнивании множественной последовательности геномов в вычислительной биологии. Определение MUM и других потенциальных якорей является первым шагом в более крупных системах выравнивания, таких как MUMmer. Анкеры - это области между двумя геномами, где они очень похожи. Чтобы понять, что такое MUM, каждое слово в аббревиатуре можно разбить по отдельности. Соответствие подразумевает, что подряд встречается в обеих последовательностях, которые должны быть выровнены. Уникальный означает, что подряд встречается только один раз в каждой последовательности. Наконец, максимум указывает, что подстрока не является частью другой более крупной строки, которая удовлетворяет обоим предварительным требованиям. Идея заключается в том, что длинные последовательности, которые точно совпадают и встречаются только один раз в каждом геноме, почти наверняка являются частью глобального выравнивания.
in the multiple sequence alignment of genomes in computational biology. Identification of MUMs and other potential anchors is the first step in larger alignment systems such as MUMmer. Anchors are the areas between two genomes where they are highly similar. To understand what a MUM is we each word in the acronym can be broken down individually. Match implies that the substring occurs in both sequences to be aligned. Unique means that the substring occurs only once in each sequence. Finally, maximal states that the substring is not part of another larger string that fulfills both prior requirements. The idea behind this is that long sequences that match exactly and occur only once in each genome are almost certainly part of the global alignment.
Алгоритм
Определение множества MUM в двух очень длинных последовательностях генома не является вычислительно тривиальным. Существует несколько алгоритмических способов подхода к идентификации MUM в многократном выравнивании последовательности. Самый простой и медленный метод - это использование грубой силы, где для каждого индекса i в геноме А и каждого индекса j в геноме В вычисляется самый длинный общий префикс (P) A[i n] и B[j m]. Далее вы должны гарантировать, что длина P составляет по крайней мере d, где d - минимальный размер MUM, указанный. Наконец, вы должны убедиться, что P уникален в обоих геномах. Таким образом, сложность метода грубой силы равна O ((mn). В действительности, хотя MUM идентифицируются путем создания обобщенного дерева суффиксов для A и B, затем создается список для всех внутренних узлов с точно одним ребенком от каждой последовательности генома. Для каждого из этих узлов ((мы будем определять детей из генома А как i и детей из генома B как j)) проверьте, что A[i 1] ≠ B[j 1] и для тех, где это условие соблюдается, мы знаем, что это MUM. В этом случае сложность уменьшается до O ((m+n). На иллюстрации ниже, с учетом начальных строк S и T и d 1, MUM должны быть G и TA. Красный лист означает, что лист пришел из строки S, а синий лист означает строку T. Внутренний узел в A был отброшен, потому что означает, что символ, который приходит перед обоими A, идентичен (T), это условие, при котором последовательности принадлежат к более крупной уникальной последовательности. Внутренний узел в C отбрасывается, потому что у него есть два ребенка от S. Это оставляет нам MUM G и TA.
Максимальная точность совпадения (MEM)
MUM являются подмножеством более крупного множества, называемого максимальными точными совпадениями или MEMS. В MEM условие уникальности MUM ослаблено. MEM похожи на локальное выравнивание, но в этом случае идентифицируют только последовательности, где нет пробелов.