We have a bioinformatician in our group, Christina Boucher, who works on succinct data structures based on de Bruijn graphs and FM-indexing/BWT. You can read the blog of one of her PhD students here; it's an interesting topic. BioRxiv pdf to the advance publication here.

Graph theorie is begin to be use to infer homology relation. But also to study gene and genome relation ship https://www.ncbi.nlm.nih.gov/pubmed/26774999 is a review (made by lab) about this subject.

Is also worth mentioning that hogenom ( a homology database host in LYON france) is done with SILIX ( which use graph theorie ).

Sequence assemblers use de Brujin graph traversal to assemble reads.

You should be able to find papers on that. I'm not at my PC at the mo so can't easily find you a reference but it's a well documented concept.

Example of use of kernels on graph nodes. Although not graph theory per se, you may be interested in how dynamic graphs can be analyzed using tensor factorization methods, see some of my notes here.