Analysis of Complex Networks

9.13 Conclusion

Graph theory is widely used in chemo- and bioinformatics, where it addresses a range of practical problems, ranging from identification of molecular similarities to the analysis of macromolecular interactions and crystal packing. Being a well-developed mathematical discipline, it saves researchers from searching for technical implementations of their computational problems, allowing them to focus on the formulation of their problems in graph theoretical terms. This, however, is not always straightforward and often represents a real challenge. Here, two main difficulties may be highlighted.

Firstly, objects in chemo- and bioinformatics are complex by nature. Graph representations of chemical molecules and, even more so, biological macromolecules should reflect both chemical and topological (3D) properties. A proper understanding of these properties is a necessary prerequisite for the development of practical algorithms within the field. A simplified description of chemical molecules as planar graphs is suitable for many purposes, however there needs to be special labeling when their chemical properties depend on a particular 3D conformation. In the case of biological macromolecules, this is yet more entangled, given that their functionality is most often associated with conformational changes.

Secondly, graph theory has size limits for the objects it works with. Many useful graph-theoretical problems, such as graph matching, are known to be NP-complete, which implies ...