Effective similarity calculation in biological databases

It is possible to explain the events occurring inside the cell, the smallest unit in living things, by observing biological networks. Similarity-based analysis is one of the techniques for biological network analysis. In this context, a database consisting of biological networks is aligned with a query network, and the networks having a similarity score higher and lower than a predefined cut-off value are separated. The exact similarity score of two networks needs to be known in the solution of this problem. Unfortunately, because of the NP-complete sub-graph isomorphism problem, this is computationally too expensive. Several methods are proposed in the literature to solve the graph alignment problem. QNET, which is one of these methods, is coded in Java using Hadoop framework in the scope of this thesis. For query networks with 7 nodes, Hadoop implementation with 10 machine cluster (18 cores) achieved 11,42 speedup. A new method called ESBiD, taking the "reference based indexing method" approach has been developed. Particularly, ESBiD focused on the weaknesses of RINQ, another reference based indexing method. To this end, by using heuristics, the number of networks in the twilight zone has been reduced by 29,85% with 93,22% accuracy, the reference network selection strategy has been changed and a new technique called "highest degree node" has been proposed in order to align the networks in the twilight zone faster. This technique reached 89,74% effectiveness in 51,14% runtime with respect to the QNET's exact alignment method. Keywords: Biological network alignment, biological database alignment, graph alignment, reference based indexing, QNET, Hadoop, ESBiD, highest degree node