When constructing an HMM from a high-order simple Markov model, there are often several states created that really represent the same position in the family of sequences, but which look different in the simple Markov model because of some slight variation in a nearby position. In some cases, the tuning of the model will favor one of the states sufficiently that simple pruning with RemoveUseless will remove the other states corresponding to the same position, but in other cases parallel paths with slight differences will remain in the model.
To reduce the size of the model, and increase its generality, it is helpful to try to identify such parallel paths and merge them together. The MergeStates operation looks for two states that have a common neighbor on the same side (that is, either both have out-edges to the neighbor, or both have in-edges from the neighbor). If the two states predict similar enough distributions for the characters, then merging the states into a single state will not increase the cost of sequences by much.
The current version of the program only considers merges between states whose connection to the neighbor is a major one (the edge count a high enough percentage of the edge counts on this side of the state), and only accepts merges for which the estimated increase in total cost for the seed sequences is less than a specified threshold (generally a few bits).
All states are checked to see what they can merge with, and merges that are sufficiently good are done. After a merge, the neighbors of the merged state are rechecked, so that nearly parallel paths can be ``zipped'' together from a common endpoint.