MUMmer
MUMmer is a bioinformatics software system for sequence alignment. It is based on the suffix tree data structure and is one of the fastest and most efficient systems available for this task, enabling it to be applied to very long sequences. It has been widely used for comparing different genomes to one another. In recent years, it has become a popular algorithm for comparing genome assemblies to one another, which allows scientists to determine how a genome has changed after adding more DNA sequence or after running a different genome assembly program. The acronym "MUMmer" comes from "Maximal Unique Matches", or MUMs. The original algorithms in the MUMMER software package were designed by Art Delcher, Simon Kasif and Steven Salzberg. Mummer was the first whole genome comparison system developed in Bioinformatics. It was originally applied to the comparison of two related strains of bacteria.
The MUMmer software is open source and can be found at the MUMmer home page. The home page also has links to technical papers describing the system. The system is maintained primarily by Steven Salzberg and Arthur Delcher at Center for Computational Biology at Johns Hopkins University.
MUMmer is a highly cited bioinformatics system in the scientific literature. According to Google Scholar, as of early 2013 the original MUMmer paper (Delcher et al., 1999) has been cited 691 times; the MUMmer 2 paper (Delcher et al., 2002) has been cited 455 times; and the MUMmer 3.0 article (Kurtz et al., 2004) has been cited 903 times.
Overview
What is MUMmer?
Do you wonder, how you are related to a monkey? If the answer is yes, I can tell you that there are algorithms in which you can find that answer. An algorithm such as “Edit distance” (by Wunch and Needleman) might come to mind; which can be used for this same topic. However, the “Edit distance” algorithm is used to compare small sequences, it would take a long time to compute genome alignments.
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). Back then 4Mb of memory was a huge deal; so, they had to do something about that, like creating this type of algorithms. Researchers have been creating algorithms to compare genome sequences. Mummer is a fast algorithm mostly used for the rapid alignment of entire genomes.
MUMmer, as mentioned before, is the system/process for efficient alignment of big-size sequences, this algorithm has been used to make discoveries about genome structure. The algorithm is really well designed and it is capable of comparing alignments within seconds. Since this algorithm is relatively new, has four versions, each one better than the previous one.
Versions of MUMmers
MUMmer1
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), 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.
MUMmer 2
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).
MUMmer 3
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” the tree described in the article “Reducing the space requirement of suffix trees”.
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.
MUMmer 4
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). Thanks to this, the suffix tree can be built once and constructed again after running it from the saved suffix tree.
Software - Open Source
MUMmer has open-source software. The best way to begin playing with this package is to go to the website given below.
This page talks about the open-source, requirements and steps to the installation, the process to run the package, and some examples of running sequences. There is more information on this website. If you get stuck, the website has information on who to contact in those cases. This page has valuable information to work with this algorithm.
Related Topics
There are other types of sequence alignments, some of the related topics are shown below:
- Edit distance
- BLAST
- Bowtie
- BWA
- Blat
- Mauve
- LASTZ
- BLAST