Visualizing Co-Phylogenetic Reconciliations

Speaker

Diego Mariottini & Maurizio Patrignani – Roma Tre University

When

Friday, Sept 22nd at 5:30 PM

Where

Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

Abstract

We introduce a hybrid metaphor for the visualization of the
reconciliations of co-phylogenetic trees, that are mappings among the
nodes of two trees. The typical application is the visualization of the
co-evolution of hosts and parasites in biology. Our strategy combines a
space-filling and a node-link approach. Differently from traditional 
methods, it guarantees an unambiguous and ‘downward’ representation 
whenever the reconciliation is time-consistent (i.e., meaningful). We address
the problem of the minimization of the number of crossings in the 
representation, by giving a characterization of planar instances and by 
establishing the complexity of the problem. Finally, we propose heuristics
for computing representations with few crossings.

Joint work Tiziana Calamoneri and Valentino Di Donato

The paper will be presented at the forthcoming 25th International Symposium on Graph 
Drawing & Network Visualization (GD 2017, https://gd2017.ccis.northeastern.edu/) and 
at the forthcoming 18th Italian Conference on Theoretical Computer Science (ICTCS 
2017, http://ictcs2017.unina.it/).