International Symposium on Discrete Mathematics and Mathematical Biology

Abstracts for the talks

Gunnar Brinkmann
Ghent University, Belgium
Structure generation: applications, methods, problems and solutions

See the PDF abstract.

Stefan Grünewald
CAS-MPG Partner Institute for Computational Biology (PICB), China
The quartet distance between phylogenetic trees and an application beyond phylogenetics

In phylogenetic data analysis, using different methods or different data sets frequently results in different trees with the same label set. Further, some heuristic optimization algorithms require the construction of a different but not too different tree from a given one, in order to find a (locally) optimal tree. Therefore, we have to quantify the dissimilarity between two phylogenetic trees with identical leaf sets.

One common measure for this is the quartet distance. It is defined to be the number of sets of exactly four taxa for which the trees have different restrictions. Bandelt and Dress showed in 1986 that the maximum distance between two binary trees, when normalized by the number of all 4-sets, is monotone decreasing with n. They conjectured that the limit of this ratio is 2/3 which corresponds to the distance between two random trees.

I will give a generalization of the conjecture to arbitrary X-trees and show some partial results. As a consequence, we find that quartets can be used to quantify the dependence between two real-valued random variables or between two data sets. In some sense, this measure of dependence corresponds to Kendall's tau to measure correlation.

Ib Madsen
University of Copenhagen, Denmark
Real algebraic K-theory

To an exact category with duality C,I will construct a spectrum K(C) with an action of Z/2 such that the fixed point spectrum is the K-theory of non singular hermitian forms when the category is the category of finitely generated projective modules with standard duality.
The construction uses a Real version of Waldhausen's S.-construction.There are Real versions of Waldhausen's basic theorems e.g.of the additivity theorems.
The bigraded homotopy groups associated to the Z/2 spectrum generalizes earlier work of Karoubi and Schlichting.
Tha talk represents joint work with Lars Hesselholt.

Vincent Moulton
University of East Anglia, United Kingdom
30 years of tight-spans and still going strong!

In 1984 Andreas Dress published a paper entitled "Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups" in response to a question raised in the late 1970's by Manfred Eigen. At that time Manfred Eigen was trying to fit 20 distinct t-RNA sequences of the E.coli bacterium onto a tree. He realized that there was an obstruction to finding such a tree even for four sequences and wondered:
What could be used as a substitute for a tree if no globally fitting tree existed? In this talk, we will explore some consequences of Andreas Dress' response, which has led to a surprising number of new theorems, unsuspected applications, and unforseen relationships with other subjects in mathematics, a few of which we will present.

Kay Nieselt
Universität Tübingen, Germany
The SuperGenome, a new concept for comparative genomics and beyond

Next-generation deep-sequencing (NGS) has been revolutionizing eukaryotic and prokaryotic genome analyses. The technology can be used to address a wide variety of questions, such as the evolution of species by comparison of their genomes.
When genomes are compared based on genomic positions typically a specific reference genome is assigned which acts as the coordinate system for the comparison. However, rearrangements and insertions or deletions lead to substantial architectural variations between genomes and therefore genomic regions, that cannot be aligned to the reference, are lost.
We have proposed the SuperGenome as a solution, which establishes a general global coordinate system for multiply aligned genomes.
This enables the consistent placement of genome annotations in the presence of insertions, deletions, and rearrangements.
In my talk I will first formally introduce the SuperGenome concept and then turn to various applications. One is GenomeRing, a visualisation of a multiple genome alignment based on the SuperGenome. With GenomeRing, we won the most creative algorithm award at Illumina's iDEA challenge 2011. The second one explains how the SuperGenome can be used as a general support for genome annotation pipelines. In particular, I will point out how the Pan-genome, i.e., the full complement of genes in a species, can be nicely derived from the SuperGenome.
Finally I will show how the SuperGenome can also be used for comparative transcriptomic analyses, notably how we have used the SuperGenome for the cross-genome prediction of transcription start sites from RNA-seq data [2].
I will end my talk by pointing out open questions that we hope to be able to solve in future research work.

[1] Herbig A., Jäger G., Battke F. and Nieselt K. (2012), "GenomeRing: alignment visualization based on SuperGenome coordinates", Bioinformatics. Vol. 28(12), pp. i7-i15, doi:10.1093/bioinformatics/bts217.
[2] Dugar G., Herbig A., Förstner K., Heidrich N., Reinhardt R., Nieselt K. and Sharma C. (2013), "High-resolution transcriptome maps reveal strain-specific regulatory features of multiple Campylobacter jejuni isolates", PLoS Genet 9(5):e1003495.

Mike Steel
University of Canterbury, New Zealand
Ancestral reconstruction, lateral gene transfer, and the joys of leaping between trees

In part 1, I will present some recent results with Olivier Gascuel on how accurately we can expect to predict ancestral states at the interior nodes of a phylogenetic tree from discrete character data at the extant leaves.

In part 2, I will describe a second project on species tree reconstruction when genes have evolved under a simple model of random lateral gene transfer (LGT). The aim is to answer questions such as: 'could we reconstruct a species tree on (say) 200 species from a large number of gene trees, if each gene has been laterally transferred into other lineages, on average, ten times?' and 'can LGT lead to inconsistent tree estimation?'
Our analysis involves a curious connection to random walks on cyclic graphs.

Dragan Stevanović
University of Niš, Serbia, and University of Primorska, Slovenia
Principal eigenvector potpourri

I will speak about my three recent results (two applied, one theoretical) which all rely on the properties of the principal eigenvectors of (different) graph matrices.


Date and Location

August 26 - 27, 2013
Max Planck Institute for Mathematics in the Sciences
Inselstraße 22
04103 Leipzig
see travel instructions

Scientific Organizers

Jürgen Jost
Max-Planck-Institut für Mathematik in den Naturwissenschaften

Peter Stadler
Leipzig University
Interdisciplinary Centre for Bioinformatics

Administrative Contact

Antje Vandenberg
Max Planck Institute for Mathematics in the Sciences
Contact by Email

05.04.2017, 12:42