Apllications of Graph Theory in Next Generation Sequencing

[martin_313]

Hello everyone,

I'm a math student interested in graph theory and its applications in biology. Sadly, biomathmeatics and bioinformatics in general are somewhat neglected at my university.

During my next semester, I'll have 2-3 months to write a paper on a topic of my choosing and I've thought about doing something relaxted to Next Generation Sequencing.
I'm currently doing an out-of-university-internship where I have to work with some Next Generation Assembly programs, so I've heard of De Bruijn Graphs and their role in assembly. However, I am not sure whether this topic by itself would be complex enough to devote my whole paper to it, so I'm currently looking for further ideas for a possible topic.
Can anyone point me to other areas of Next Generation Sequencing / genetics / bioinformatics where graph theory is applied?

Thank you for your answers
Martin

[steven]

Recently a nice review was suggested to learn about genome assembly using De Bruijn graphs. You may want to look at transcriptome assembly too. I would say that there is quite a lot to read and write on graphs for NGS.
Graphs are used in many applications.. right away I would cite "splicing graph" for instance, but as Directed Acyclic Graphs can easily substitute Hidden Markov Models you may find them in problems like gene finding or multiple alignment.
I would browse pubmed, like this for instance or like this.

Now maybe others will contribute with better propositions..

Anyway, thanks for your interest, good luck and enjoy!

[rskr]

Sadly Graph Theory doesn't help very much in biology. Graph applications on the other hand are very valuable. If you know what I mean.

[alec]

There has been some use of graph theory in haplotyping. See:

http://dx.doi.org/10.1007/3-540-44676-1_15
http://bioinformatics.oxfordjournals.../i153.abstract