Algorithmic Methods in Comparative Genomics
Organizer and Chair:
Max Alekseyev (University of South Carolina)
[
PDF]
 MAX ALEKSEYEV, University of South Carolina
Genome rearrangements: when intuition fails [PDF]

Genome rearrangements are genomic "earthquakes" that change the chromosomal architectures. The minimum number of rearrangements between two genomes (called "genomic distance") represents a rather accurate measure for the evolutionary distance between them and is often used as such in comparative genomics studies.
In this talk I shall describe an unexpected phenomenon in genome rearrangements analysis that the weighted genomic distance designed to bound the proportion of transpositions (that are complex rearrangements rarely happening in reality) in rearrangement scenarios between two genomes does not actually achieve this goal.
 BAHAR BEHSAZ, Simon Fraser University
Turing Universality of DNA SelfAssembly Models at Temperature 1 [PDF]

Selfassembly is a bottomup process in which a small number of components \textit{automatically} assemble together to form a more complex structure. Winfree introduced the Tile Assembly Model (TAM) as a simplified mathematical model of the DNA selfassembly, in which a tile may be added to the growing structure if the total interaction with its neighbors exceeds a parameter \textit{Temperature}. An interesting question is whether TAM at temperature 1 is Turing Universal, i.e., it can simulate an arbitrary Turing machine. We investigate the computational power of some variants of TAM and will show that with simple modifications Turing Universality is achievable.
 PATRICIA EVANS, University of New Brunswick
Finding RNA structure motifs [PDF]

This talk examines computational problems based on comparing RNA sequences with respect to their bond structure. We include an overview of the different computational models and input characteristics which arise in different applications, and pay particular attention to ones applicable to finding structure motifs, considering which restrictions make the problem tractable and lead to efficient algorithms.
 DAVID SANKOFF, University of Ottawa
Fractionation, rearrangement, consolidation and reconstruction [PDF]

After whole genome duplication in a species, two different mechanisms operate simultaneously to scramble gene order. One consists of rearrangement events: inversion, reciprocal translocation, transposition and chromosome fusion/fission. The other is fractionation: duplicate gene loss on a massive scale, alternately affecting the two duplicated (homeologous) regions. Serious biases result if we analyze such genomes in terms of chromosomal rearrangements only. We analyze fractionated genomes in three steps: consolidation of common (but incomplete) intervals in the descendant genomes, reconstruction of an ancestor where the genes are replaced by consolidated intervals, and intervalinternal sorting.
 JIJUN TANG, University of South Carolina
Binary Encoding and Genome Rearrangement Analysis [PDF] [SLIDES]

Genome rearrangements have been widely used in phylogenetic
reconstruction. Compared to sequence data, analyzing
these events is mathematically more difficult. To overcome this problem, encoding
genomes into binary sequences was proposed with
limited success. We revisited the idea of encoding by using
maximumlikelihood and a model that better fits the evolution of gene orders.
Similar to the model first proposed by Dr. Sankoff, our model is biased as adjacencies can
be easily broken than being restored. Our new approach achieved very good performance in both speed and accuracy, and can cope with datasets which no existing methods can handle.