Bioinformatics And Graph Algorithms

Question

[Lissa]

i am new to Bioinformatics, and would like to know what are the most popular problems that are solved using graph algorithms?

Answer 1

[Haibao Tang]

There are a whole range of problems that graph theory can be applied. Just the tip of the iceberg below.

• Genome assembly. Graph theory is used in generations of assembly softwares, in the form of overlap graph and de brujin graph. See introductory slides here and here, respectively.

• Study of genome rearrangements. Sorting the most parsimonious genome rearrangement scenario requires resolving breakpoint graph. See work in comparing mammalian genomes.

• Structure prediction of RNAs and proteins. Adjancency of residues in RNA or protein structures can be described in contact graph. In addition, graph decomposition is used to solve modular components or motifs (for example, pseudoknot).

• Graph-based clustering. This can be useful for finding motifs in protein-protein interaction network or protein families in sequence similarity graph. Some tools (e.g. MCL) can generate motifs or clusters by simulating flows inside the network.

• Graph layout algorithm can be used to visualize large-scale metabolic pathway or phylogenetic trees/networks.

• Many other bioinformatics problems can be conceptually reduced to graph representations. Graph traversal, coloring, clique enumeration, matching, flow, minimum spanning tree, shortest path etc. can then be used to solve miscellaneous problems.

Answer 2

[Bilouweb]

Hello.

I used Graph algorithm to solve the protein threading problem. But, obviously, graphs are mostly used in gene/protein interaction networks.

Answer 3

[Egon Willighagen]

Any problem that involves atoms and bonds in bioinformatics are solved using graph theory. So, anything to do with force fields (Molecular Dynamics, Molecular Modeling), comparing molecular structures (metabolite identification, enzyme reaction mechanisms), etc, etc are all solved with (chemical) graph theory.

These graph theory use cases are so common, you would not even call them popular anymore.

Answer 4

[Rm]

Some of the interesting publications you can look:

Prediction of functional sites in proteins using conserved functional group analysis.

A graph-theory algorithm for rapid protein side-chain prediction.

Improved microarray-based decision support with graph encoded interactome data.

Recent review: Building a parallel between structural and topological properties.

Answer 5

[Gww]

Isoform specific expression estimation from RNA-Seq data uses graph theory.

Splicing graph analysis of pre-mRNA splicing can also be reduced to a graph problem. The exons in a gene can be thought of nodes and their splicing partners can be thought of as edges.