In this class we have already seen two applications of graph theory to Bioinformatics. One was Eulerian circuits and the other was minimum spanning trees. You can find the reference in the Lectures page and these should be good starting points. The focus of this project should be on use of graph theory in Bioinformatics. Ask Amin for relevant publications.