Reconstructing the pre-doubling genome

Genome duplication is an important source of new gene functions and novel physiological pathways. In the course of evolution, the nucleotide sequences of duplicated genes tend to diverge through mutation, so that one copy loses function (and disappears from view) or develops a new function, encoding a distinct but similar product. Originally a duplicated genome contains two identical copies of each chromosome, but through reciprocal translocation, parallel linkage patterns between the two copies are disrupted. Eventually, all that can be detected are several chromosome segments of greater or lesser length (blocks), each of which appears twice in the genome, containing many paralogous genes in parallel orders. We present an exact algorithm for reconstructing the ancestral pm-doubling genome in polynomial time, minimizing in key cases the number of translocations required to derive the observed order and orientation of blocks along the present-day chromosomes. We apply this to the genome duplication which has been described for Saccharomyces cere- visiae.