Chordal Graphs: An adequate model for some biological problems.
Chordal graphs constitute an important and well studied graph family. They are an useful tool to study many problems. A chord in a cycle is an edge between two non-consecutive vertices in the cycle. A chordal graph is a graph such that each one of its cycles contains a chord.
Modern science has shown that all species of organisms that live on earth undergo a slow transformation process through the ages. This process is called evolution. One of the central problems in biology is to explain the evolutionary history of today’s specie. This is usually done by constructing trees whose leaves represent present-day species and whose interior nodes represent hypothesized ancestors. These kinds of trees are called phylogenetic trees.
More general, we can build phylogenetic trees for species, populations, proteins or objects.
We will concerned with objects described by the state they exhibit on a set of characteristics, let M be the character state matrix with n rows (objects) and m columns (characters). Thus Mij denotes the state the object i has for character j . The goal is construct a tree T whose leaves are objects and with the property that for each state s of each character c, the set of nodes of T for which the state is s with respect to c must form a subtree of T. If such a tree exists it is said that M admits a perfect phylogeny. Given a character state matrix is constructed a graph called SIG. For each state of each character we create a vertex in the SIG. Note that for each vertex of the SIG there is a set of objects that have that state for that character. Then we create an edge between two vertices of SIG if and only if the corresponding sets have nonempty intersection. This is why this graph is called state intersection graph. Observe that each clique (maximal complete) of SIG is related with an object that presents these states in these characteres.
It is natural to model this problem with chordal graphs because it is known that they are exactly the intersection graph of subtrees in a tree. Moreover, it was proved that if G is a chordal graph and C(G) is the family of cliques of G there is a tree T whose vertex set is C(G) and for each vertex v of G , the set of cliques of G that contain v is a subtree of T. Such a tree is called a clique tree of G.
Chordal graph can be used in other field as protein interactions. Most cellular processes are carried out by multi-proteins complexes, groups of proteins that bind together to perform a specific task. Some proteins form stable complexes, while other proteins form transient association and are part of several complexes in different stages of a cellular process. A better understanding of this higher-order organization of proteins into overlapping complexes is an important step to unveiling functional and evolutionary mechanisms behind biological networks. This situation can be modeled by a graph where the vertices are proteins and two vertices are connected by an edge if the corresponding proteins interact. Complex proteins can be seen as cliques of this graph. Then, when
the graph is chordal, a clique tree and the family of subtrees representing the vertices, gives us a good framework for following the activity of a protein in different complexes .
In this work we analyze well known properties of clique trees. We present different parameters and show some relations between them. We think that our results could have interest in biological problems as cited before or in others problems.