# 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.

References:

[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

Germany

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