Maximal unique match
A maximal unique match or MUM, for short, is part of a key step Formal Definition. "Given two genomes A and B, Maximal Unique Match (MUM) substring is a common substring of A and B of length longer than a specified minimum length d (by default d = 20) such that Algorithm. Identifying the set of MUMs in two very long genome sequences is not computationally trivial. There are several algorithmic ways to approach identifying MUMs in multiple sequence alignment. The simplest and slowest method is using brute force where for every index in genome and every  index in genome , you calculate the longest common prefix of and . Next you must guarantee that the length of is at least where is the minimum MUM size specified. Finally you must ensure that is unique in both genomes. The complexity of the brute force method is thus . In actuality though MUMs are identified by building a generalized suffix tree for and . A list is then created for all internal nodes with exactly one child from each genome sequence. For each of these nodes(we will identify children from genome as and children from genome as ) check that and for those  where this conditions holds, we know this is a MUM. In this case the complexity is reduced to . In the illustration below given the initial strings and and a of 1, the MUMs should be G and TA. A red leaf denotes that the leaf came from string S and a blue leaf denotes string . The internal node at A was discarded because meaning the character that comes before both A's is identical (T), this is condition where the sequences belongs to a larger unique sequence. The internal node at C is discarded because it has two children from  S. This leaves us with the MUMs of G and TA. Example. To illustrate MUMs further, we take the following example. Let's say that d=3 and our two genomes are as follows: Working through the sequence our first MUM that satisfies the conditions occurs here: TGT is at least d in length, occurs only once in both sequences, and the characters to the left and right differ between genomes. To illustrate an example where expansion is needed to ensure that our MUM is not part of a larger sequence and unique, take the following: There are two problems in  the case of testing ATG as a MUM because ATG is not unique and it is also part of a larger subsequence as illustrated here: Therefore expansion of this sequence is required in an attempt to satisfy the conditions for being a MUM as shown here. Using this method iteratively produces a final product where each MUM is identified for clarity each MUM is colored-coded: Maximal Exact Match (MEM). MUMs are a subset of a larger set referred to as Maximal Exact Matches or MEMS. In a MEM the unique condition of MUMs is relaxed. MEMs are like local  alignment but in this case only identify sequences where there are no gaps.