The aim of enumeration is to list all the feasible solutions of a given problem satisfying some constraints. Enumeration algorithms are particularly useful whenever the goal of a problem is not clear and all its solutions need to be checked. Since one peculiar property of biological networks is the uncertainty, a scenario in which enumeration algorithms can be helpful is biological network analysis. Modelling biological networks indeed introduce bias: arc dependencies are neglected and underlying hyper-graph behaviours are forced in simple graph representations to avoid intractability. Moreover regulatory interactions between all the biological networks are omitted, even if none of the different biological layers is truly isolated. Last but not least, the dynamical behaviours of biological networks are often not considered: indeed most of the currently available biological network reconstructions are potential networks, where all the possible connections are indicated, even if edges/arcs and vertices are hardly present all together at the same time. More details about these aspects of the biological networks can be found in [8]. Our Contribution. We have shown four examples of enumeration algorithms that can be applied to efficiently deal with some biological problems modelled by using biological networks: enumerating central and peripheral nodes of a network, enumerating stories, enumerating paths or cycles, and enumerating bubbles. Notice that the corresponding computational problems we define are of more general interest and our results hold in the case of arbitrary networks.
Structural analysis allows the identification of important and not important vertices within a network and also for this reason has become very popular in many disciplines. In the biological domain, the importance of a vertex can be defined in many different ways. With neighbourhood-based centrality measures, such as degree, the importance of the vertices is inferred from their local connectivity and the more connections a vertex has the more central it is. Closeness, eccentricity, and shortest path based betweenness relies on global properties of a network, such as distance between vertices. ? The author wants to thank the PhD advisor Pierluigi Crescenzi, the PhD School of Dipartimento di Sistemi e Informatica, Universita` di Firenze (Italy), and all the coauthors of the papers.
We have focused on the enumeration of the radial and diametral vertices, i.e. vertices that are central and peripheral according to the eccentricity notion of centrality, and on the computation of the radius and diameter of biological networks and of real world graphs in general. The diameter and radius of a graph are respectively the maximum and minimum eccentricity among all its nodes, where the eccentricity of a node x is the distance from x to its farthest node. Thus, intuitively, the diametral source vertices are the vertices that hardly reach the other ones, the diametral target vertices are the vertices hardly reachable from the other ones, and the radial vertices are the vertices that easily reach all the vertices of the network. In order to calculate the vertices that can be easily reached from any other vertex, it is sufficient to consider the transposed graph.
We have presented the difub Algorithm, which is able to list all the diametral sources and targets and to compute the diameter of (strongly) connected components of a graph G = (V, E) in time O(|E|) in practice, even if, in the worst case, the complexity is Θ(|V ||E|). Analogously, we have presented a new algorithm to list all the central vertices and to compute the radius of (strongly) connected components of a graph in almost O(|E|) time in practice.
The analysis of real world networks in general, such as citation, collaboration,
communication, road, social, and web networks, has attracted a lot of attention.
The fundamental analysis measures have been reviewed in [
The problem of enumerating stories was motivated initially by the biological
question in [
A metabolic story has to capture the relationship between the vertices of interest in a way that allows us to define a flow of matter from a set of sources to a set of target compounds. The need for this hierarchy between the compounds led us to consider acyclic solutions. The maximality condition has been added in order to capture all alternative paths between the sources and the targets. The problem is then to “tell” all possible stories given as input a graph G and a subset B of the vertices of G.
We have presented a polynomial algorithm to find one story and an exact
but exponential approach for the enumeration problem [
Our contribution appeared in [
Studying paths or cycles of biological networks can be useful for several
purposes. In the case of interaction graphs, such as Gene Regulatory networks, the
importance of enumeration has been shown in [
We have considered the problem of enumerating paths and cycles in the case of undirected graphs. This result can be useful for undirected Protein-Protein Interaction networks, where nodes are proteins and edges are interactions, but in the case of interaction networks in general, our approach neglects the effects of the controls, i.e. the sign and direction of the arcs. In this latter case, the cycles can be enumerated in the underlying undirected graph and a posteriori filtered or ad hoc algorithms can be applied. The main question arising from our work, is whether it is possible to extend our result to directed graphs in order to efficiently deal also with this kind of networks.
On the other hand, our contribution is not just restricted to biological
undirected networks, but extends also to arbitrary undirected graphs. Listing all
the paths and cycles in a graph is a classical problem whose efficient
solutions date back to the early 70s. The best known solution in the literature
is given by Johnson’s algorithm [
We have presented the first optimal algorithm to list all the paths and cycles in an undirected graph G. Our algorithm requires O(|E| + Pc∈C(G) |c|) time and is asymptotically optimal: indeed, Ω(|E|) time is necessarily required to read G as input, and Ω(Pc∈C(G) |c|) time is necessarily required to list the output. Moreover, our algorithm lists all the (s, t)-paths in G optimally in O(|E| + Pπ∈Pst(G) |π|) time, observing that Ω(Pπ∈Pst(G) |π|) time is necessarily required to list the output.
Our algorithm exploits the decomposition of the graph into biconnected
components and without loss of generality restricts to study paths and cycles in a
same biconnected component. Thus it recursively lists the cycles or (s, t)-paths
using the classical binary partition: given an edge e in G, list all the solutions
containing e, and then all the solutions not containing e, at each time modifying
the graph. In order to avoid recursive calls (in the binary partition) that do not
list solutions, we have used a certificate, as a data structure, whose cost for
dynamically updating is constant with respect to the number of solutions produced.
In order to prove the complexity obtained, we have exploited the properties of
the binary recursion tree corresponding to the binary partition. For more details,
see [
A DNA fragment, that is an RNA-coding sequence, is transformed in a
PremRNA sequence, through the transcription phase, in which sequences of exons
and sequences of introns alternatively occur. The removal of all the sequences
of introns and of some sequences of exons leads to the mRNA sequence, that
is a protein-coding sequence, that translated leads to a protein. Since not any
exon is transcribed in the mRNA sequence, there can be many possible mRNA
sequences. For instance, let he1, i1, e2, i2, e3, i3, e4, i4i be a fragment of DNA,
where for any j, with 1 ≤ j ≤ 3, ej and ij are the j-th sequence of exons
and introns respectively. The possible resulting mRNA sequences containing e1
are he1, e2, e3, e4i, he1, e2, e3i, he1, e2, e4i, he1, e3, e4i, he1, e2i, he1, e3i, he1, e4i.
The underlying phenomenon is called alternative splicing and checking all the
alternative events has been shown in [
Since the k-mers correspond to all words of length k present in the reads
(strings) of the input dataset, and only those, in relation to the classical de Bruijn
graph for all possible words of size k, the de Bruijn graph for NGS data may
then not be complete. We have ignored all the details related to the treatment
of NGS data using De Bruijn graphs, and consider instead the more general
case of finding all (s, t)-bubbles in an arbitrary directed graph. In particular we
show the first linear delay algorithm to identify all bubbles. A previous known
algorithm presented in [