MUMmer

Genomes are a large sequence of genetic instructions/information about an organism (in a chromosome); now, imagine “comparing a 4 Mb sequence such as M. Tuberculosis to another 4 Mb sequence, many algorithms either run out of memory or take too long to complete” (Arthur et al., 1999).[4]Researchers therefore have been creating algorithms capable of comparing genome sequences. Mummer is a fast algorithm mostly used for the rapid alignment of entire genomes. The MUMmer algorithm is relatively new and has 4 versions.

MUMmer1 or just MUMmer consists of three parts, the first part consists of the creation of suffix trees (to get MUMs), the second part in the longest increasing subsequence or longest common subsequences (to order MUMs), lastly any alignment to close gaps.

To start the process, as a reminder, we need to get two Genomes as input. Once we receive them, we are going to search for the maximal unique matches (MUMs). MUMs’ algorithm has its own logic since it can be done in several ways. For instance, the naïve algorithm goes through all the sequences from one genome and compares it with the other sequences, which takes O(m*m2) which m and m2 are the two genomes. However, since MUMmer has to be fast, it uses the data structure called suffix tree (Suffix tree) which takes O(m+m2). From this tree, we extract the MUMs (which are the subsequences that are represented by one internal node by both sequences).

Once we identify the MUMs, we need to choose a genome and sort (and possibly remove) the MUMs based on the position of the other genome. This step can be done easily by choosing a genome and enumerate the nodes (MUMs) in ascending order, and the other one we enumerate each node according to the node from the first sequence. In other words, we enumerate a pair of MUMs (with the exact match from both genomes) with the same value regardless of the position. Then we sort. To make this happen, we can choose any of the methods available. For example, this can be done with Long Common Subsequence (Longest common subsequence problem) or Long Increasing subsequence(LIS). At the end of this process, the MUMs on both sequences are aligned/ordered equally (some MUMs are ignored for now, since we cannot have a value enumerated with a big number before one enumerated with a small number). The best time complexity for this step is O(nlogn).

Finally, we have to deal with the interruption between MUMs-alignment, which may be known as gaps. We employ other alignment algorithms that can fill these gaps. Arthur and his team (Arthur et al., 1999),[4] mention that the gaps fall in the following four classes:

• An SNPinterruption – when comparing two sequences, one character will differ. In other words, characters before and after that character will be equal.
• An insertion – when comparing two sequences, there is a subsequence in only appears in one of the sequences. It would be an empty gap in the other sequence at the moment of comparison of the two sequences.
• A highly polymorphic region – when comparing two sequences, there can be found a subsequence in which every single character differs.
• A repeat – it’s the repetition of a sequence. Since MUMs can only take unique sequences, that gap can be one repetition of one of the MUMs.

This algorithm was redesigned to require less memory, and the process runs faster and is more accurate than the first one. It also allows for bigger genomes alignment.

The improvement was the amount stored in the suffix trees by employing the one created by Kurtz. For this tree, the insertion is different since it is just a plugin of just one sequence, the other one is more to compare (is like adding it, but we are not, we are comparing the characters within the tree). It reduces space complexity since it is storing one sequence.

Finally, the first MUMmer algorithm only aligned the two sequences and jumped to another step. However, to achieve better coverage, the MUMs sequences are becoming clusters (meaning that is a group of MUMs that are separated with a smaller number of gaps).

According to Stefan Kurtz and his teammates, “the most significant technical improvement in MUMmer 3.0, is a complete rewrite of the suffix-tree code, based on the compact suffix- tree representation of” [5] the tree described in the article “Reducing the space requirement of suffix trees”.[6]

Another improvement was the relaxation of the MUMs. This means that now the user has the option of finding all non-unique maximal matches, all the matches that are unique only in a chosen sequence, or original MUMs (which are unique for both sequences). This was added to avoid some kind of missing subsequences that were copies of MUMs.

According to Guillaume and his team, there are some extra improvements in the implementation and also innovation with Query parallelism. The first, and biggest, improvement is the raise of the size limit for the sequence is being tested. Finally, “MUMmer4 now includes options to save and load the suffix array for a given reference”(Marcais et al., 2018).[7] Thanks to this, the suffix tree can be built once and constructed again after running it from the saved suffix tree.