Genome Rearrangement and Planning

Abstract

The genome rearrangement problem is to find the most eco-nomical explanation for observed differences between the gene orders of two genomes. Such an explanation is pro-vided in terms of events that change the order of genes in a genome. We present a new approach to the genome re-arrangement problem, according to which this problem is viewed as the problem of planning rearrangement events that transform one genome to the other. This method differs from the existing ones in that we can put restrictions on the num-ber of events, specify the cost of events with functions, pos-sibly based on the length of the gene fragment involved, and add constraints controlling search. With this approach, we have described genome rearrangements in the action descrip-tion language ADL, and studied the evolution of Metazoan mitochondrial genomes and the evolution of Campanulaceae chloroplast genomes using the planner TLPLAN. We have ob-served that the phylogenies reconstructed using this approach conform with the most widely accepted ones.