I often use inverse interval graphs to represent biologically relevant features along a genomic sequence. For example, given a (relatively) small genomic region, the graph would contain a node for each gene in the region, and there would be an edge between two nodes if the corresponding genes do not overlap (the complement of the interval graph).
I recently implemented a program that uses the Bron-Kerbosch algorithm to list all maximal cliques for an inverse interval graph corresponding to a small genomic region. This algorithm has an exponential complexity, but I didn't worry about it at first since I didn't expect more than a handful of genes to be present in a given region. However, I have since encountered a few cases in my data that the Bron-Kerbosch algorithm cannot handle in a reasonable amount of time or space.
This Wikipedia article mentions several alternatives to the Bron-Kerbosch algorithm that have a polynomial complexity as long as the number of cliques is polynomially bounded. I have begun looking into Chiba & Nishizeki's algorithm as a possible alternative, but the formulation is very dense. Before I spend too much time looking into this, I wanted to ask two questions.
- First, since my graph is an inverse interval graph and not an interval graph, am I actually guaranteed polynomial runtime with these alternative algorithms?
- Second, assuming I do want to implement one of these alternative algorithms, do any of them have available reference implementations? I don't expect a reference implementation to work out of the box with my problem, but it would be extremely helpful when trying to adapt the algorithm for my program.