Graph Theory for Systems Biology: Interval Graphs, Motifs, and Pattern Recognition

Friday, November 20, 2015 - 11:30am - 11:45am
Keller 3-180
John Jungck (University of Delaware)
Interval graphs are interesting cases because a biologist first developed them, and the formal mathematics to explore them was developed later. Interval graphs have a variety of biological applications across broad samplings of phylogenetic diversity, spatial and temporal scales, and diverse biological mechanisms. An important property of interval graphs is that their maximal cliques can be ordered in sequence in such a way that for any vertex (interval) v, the maximal cliques containing v occur consecutively in the sequence. Biological examples of interval raps include restriction maps, complementation maps, protein and nucleic acid sequences, deletion maps, chromosomal linkage maps, some gene expression maps, and some niche spaces of food webs. We have developed four software packages for handling biological data using interval graph-theoretic techniques: (a) javaBenzer and (b) BioGrapher with only passing reference to (c) PC-tree (currently lacking a data interface), and (d) javaBenzer FoodWeb. JRJ will present four examples based upon actual biological data: a DNA restriction map, a yeast gene expression microarray analysis, a food web with an energy flux analysis, and a breast cancer gene expression network.


John R. Jungck and Rama Viswanathan, Graph Theory for Systems Biology: Interval Graphs, Motifs, and Pattern Recognition. In: Raina Robeva, editor, Algebraic and Discrete Mathematical Methods for Modern Biology, Burlington: Academic Press, 2015, pp. 1-27.

The Biological ESTEEM Project (