| Project | Rearrangements in genomes with unequal content |
|---|---|
| Date | 21/07/05 |
| Version | 1.0 |
| Purpose of Meeting | Discuss solution proposal |
| Supervisor present | Leong Hon Wai |
Prof Leong pointed out that the MGR algorithm is essentially a greedy algorithm which selects an operation which maximizes the decrease in the distances between the genomes. Having a clear idea of the general framework of the algorithm allows us to consider different approaches/improvements.
One approach is to augment the distance computation to take into account evolutionary events such as the insertion and deletion of continuous segments of the genomes. Another approach would be to stick to the same set of events but modify the distance computation such that it will take only take into account the markers that are common to the two genomes being compared. This generalised notion of the rearrangement distance allows us to compare genomes with different content. This implies that during the reconstruction, the gene content of an ancestral genome will be that of the intersection of all of its leave nodes.
Since the second approach is easier to implement, we decided to develop a prototype based on the second approach by adapting of the code for the original algorithm.
Prof Leong mentioned that instead of always looking at one operation in each step of the algorithm one possible improvement is to look at two operations at a time. This expands the set of neighbors of a solution and may allow us to discover more optimal trees.