CHAPTER 10
GRAPHS IN BIOINFORMATICS
10.1 GRAPH THEORY—ORIGIN
Graph theory emerged in 1736 when Euler addressed the problem of walking across the seven bridges of Königsberg without crossing any bridge twice [1]. Euler used the benefits of graph theory to conclude that it was impossible to walk through the city crossing each bridge only once. A century later, graphs were applied to recreational mathematical problems [2] such as the Knight’s Tour and the Icosian Game [3]. Representing graphs in the form of dots and lines emerged out of 19th century chemistry, with the introduction of the term graph into both the chemical and mathematical literature by Sylvester [4], with a molecule represented by the connectivity between its constituent atoms. Since then, graphs have been applied successfully to diverse areas such as chemistry, operations research, computer science, electrical engineering, and drug design. More recently, graph theory has been used extensively to address biological problems. After a brief introduction to graph theory and the generic solution set commonly applied to several fields, we present select recent applications of significance in bioinformatics.
10.1.1 What is a Graph?
A graph is a set of nodes or vertices connected by a set of links, connections, or edges. This is represented mathematically as G = (V, E), where V represents the vertices and E represents the edges [5]. Two vertices are said to be adjacent if there is an edge ...
