Genome rearrangement algorithms in statistical and biological perspectives
Speaker: David Sankof , Univ of Ottawa
Date: September 11 2006
Time: 11:30AM to 1:00PM
Location: TOC lab 32-G575
Host: P Clote, BC & B Berger, MIT
Contact: Kathleen Dickey, 617 253 3037, kvdickey@mit.edu
Relevant URL: http://www-math.mit.edu/compbiosem/To see whether the syntenic comparison of two genomes can reveal some signal of the specific rearrangement processes responsible for their evolutionary divergence we should carry out the rearrangement analysis of these genomes in parallel with the same analysis on pairs of randomized genomes. The total number of syntenic blocks, i.e., maximal regions homologous in the two genomes, is an indicator of the evolutionary divergence of two genomes, but contains no information about the evolutionary processes that caused this divergence.
In classical genetics, the main rearrangement events include inversions (reversals) of chromosomal segments, and reciprocal translocations of the prefixes or suffixes of two chromosomes. For a fixed number of syntenic blocks in two genomes, the number and nature of the events that intervene to differentiate them can be inferred from the number of cycles in the bicoloured graph - one colour edge for the block adjacencies in each genome - they induce.
It is these cycles induced by the two data genomes that should be assessed in comparison with those in random genomes to see if there remains an evolutionary signal. For random genomes, we have shown that the limiting expectation of the number of cycles c is
c=max[G,H]+2GH/(2G+2H-1)+1/2 log[n+min(G,H)/(G+H)],
where G and H are the number of linear chromosomes in the two genomes. We discuss how this result was built up, using simulations, random graph theory and combinatorial recurrences. The evolutionary model allows only generalized inversions (including translocations, fusions and fissions) and general block interchange (including transposition).
When no signal about the specific events is apparent, i.e., when c is not significantly large, we can at least estimate the relative proportion of inversions versus translocations for fixed n. Our estimators are based on the numbers of chromosomes in one genome sharing blocks with each chromosome in the other genome.
Part of the weekly Bioinformatics seminar series sponsored by the Mathematics Department at MIT and the Theory of Computation Group at CSAIL.
See other events that are part of Bioinformatics Seminar Series 2006/2007
See other events happening in September 2006
