# Seminario del 20 Settembre 2018

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

### Relatore

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

Nessuno

### Date

Luogo | Data | Orario | Crediti (CFU) |
---|---|---|---|

Aula Magna (Collegio Raffaello) | 20 Settembre 2018 | 09:00-10:00 | 0.0625 |