Genome rearrangements reorganize the gene order in the chromosome. Usually two closely related prokaryotes share many gene clusters, which are sets of genes in close proximity to each other, but not necessarily contiguous nor in the same order in both genomes. Genes in gene clusters are functional related such that the cluster of genes in closely related organisms will appear continuously but in different order. It plays an important role in the construction of phylogenetic trees and prediction of gene functions. Thus, finding gene clusters is an important problem in comparative genomics. In this project, we will discuss gene clusters finding problem and develop its software tools. We will use the model of approximate common intervals, that is, genomes are considered as strings and gene clusters are defined as approximate common intervals in strings. At first, we will improve our O(n3) algorithm for finding approximate common intervals with set symmetric < k. And then, we will consider other definitions of approximate common intervals, such as set transformation distance. In the meanwhile, we will construct the gene finding software, and test our algorithms using real biology data. We are interesting in finding gene clusters among rice, arabidopsis and grass genomes.
