Pairwise Compatibility Graphs (Invited Talk)

Pairwise Compatibility Graphs (PCG) are graphs introduced in relation to the biological problem of reconstructing phylogenetic trees. Without demanding to be exhaustive, in this note we take a quick look at what is known in the literature for these graphs. The evolutionary history of a set of organisms is usually represented by a tree-like structure called phylogenetic tree, where the leaves are the known species and the internal nodes are the possible ancestors that might have led, through evolution, to this set of species. Edges are evolutionary relationships between species, while the edge weights represent evolutionary distances among species (evolutionary times). The phylogenetic tree reconstruction problem consists in finding a fully labeled phylogenetic tree that'best' explains the evolution of given species, where'best' means that it optimizes a specific target function. Tree reconstruction problem is proved to be NP-hard under many criteria of optimality, so the performance of the heuristics for this problem is usually experimentally evaluated by comparing the output trees with the partial trees that are unanimously recognized as sure by biologists. But real data consist of a huge number of species, and it is unfeasible to compare trees with such a number of leaves, so it is common to exploit sample techniques. The idea is to find efficient ways to sample subsets of species from a large set in order to test the heuristics on the smaller sub-trees induced by the sample. The constraints on the sample attempt to ensure that the behavior of the heuristics will not be biased by the fact it is applied on the sample instead of on the whole tree. Since very close or very distant taxa can create problems for phylogenetic reconstruction heuristics [9], the following definition of Pairwise Compatibility Graphs [12] appears natural