MiGaL is a method based on a four layers representation of thesecondary structure of an RNA.
MiGaL doesn't take into account pseudo-knots. The four levels are:
Each level is coded by a rooted ordered labelled tree. The comparison between two MiGaLs is made from the top level (0) to the bottom one (3). At each level, trees are compared using a contrained edition algorithm. The constraints correspond to the fact that a match (association) made at a level can not be contradicted later. For example, if two hairpin loops are associated at level 2, then the nucleotides of the first hairpin loop can be associated only with the nucleotides of the second hairpin loop.
The edition algorithm used to compare trees of level 0, 1 and 2 is based on 7 edit operations: substitution, deletion, insertion, node fusion, node split, edge fusion and edge split. Substitution changes the label of a node or edge (that is changes the number of nucleotides in a multiloop for example). Deletion removes nodes and edges in the first tree. Insertion (the reverse of deletion) corresponds to adding elements into the first tree. Node fusion corresponds to merging 2 nodes into the first tree, for example, merging a multiloop with one of its connected hairpin loops. Edge fusion corresponds to merging two edges into the first tree, for example, making a big helix from two helices by removing the internal loop between those helices.
To limit the time taken by the computation, we introduce a maximal number of node fusions and edge fusions that can be made on each node. Also, we have to place a control on the fusion operation: "how to choose between a node deletion and a node fusion". To control the fusion operation, the cost of the fusion is equal to the cost of the deletion plus a penality. This penality (called "tuning parameter") corresponds to the gain the fusion must allow in relation to to the solution without fusion.