On pairwise compatibility graphs

Pairwise compatibility graphs have their origin in Phylogenetic, a branch of Computational Biology,
which concerns in reconstructing evolutionary relationships among organisms. These relationships
are commonly represented as edge-weighted trees, i.e. Phylogenetic trees, and the Phylogenetic
tree reconstruction problem consists in finding the best phylogenetic tree that explains the given
set of taxa. The reconstruction problem is NP-hard under many criteria of optimality and the real
phylogenetic trees are usually huge. For this reason, it is common to extract relatively small
subsets of taxa from large phylogenetic trees for testing the reconstruction algorithms only on the
smaller subtrees induced by the sample. It has been observed that using, in the sample, very close
or very distant taxa can create problems for phylogeny reconstruction algorithms. That is, in
selecting a sample from the leaves of the tree, the constraint of keeping the distance between any
two leaves in the sample between two given positive integers dmin and dmax is used.
This motivates the introduction of pairwise compatibility graphs (PCG): given a phylogenetic tree T,
and two integers dmin,dmax we can associate a graph G, called the pairwise compatibility graph of
T, which nodes are the leaves of T and for which there is an edge between two nodes if the
corresponding leaves in T are at a weighted distance within the interval [dmin,dmax].
In this talk, the open problem consisting in demarcating the boundary of the PCG class is
underlined and the results on these graphs, known up today, are presented.


Prof.ssa Rossella Petreschi - Professore ordinario presso il Dipartimento di Informatica dell’Università “Sapienza” di Roma

Docente di riferimento

Prof. Alessandro Aldini

Vincoli di partecipazione



Luogo Data Orario Crediti (CFU)
Aula Magna (Collegio Raffaello) 20 settembre 2018 09:00-10:00 0.0625