Question: Bioinformatics And Graph Algorithms
gravatar for Lissa
8.7 years ago by
Lissa70 wrote:

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

algorithm graph • 5.8k views
ADD COMMENTlink modified 8.0 years ago by Gww2.6k • written 8.7 years ago by Lissa70
gravatar for Haibao Tang
8.7 years ago by
Haibao Tang3.0k
Mountain View, CA
Haibao Tang3.0k wrote:

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.

ADD COMMENTlink modified 8.7 years ago • written 8.7 years ago by Haibao Tang3.0k
gravatar for Egon Willighagen
8.7 years ago by
Egon Willighagen5.2k wrote:

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.

ADD COMMENTlink written 8.7 years ago by Egon Willighagen5.2k
gravatar for Bilouweb
8.7 years ago by
Saclay, France
Bilouweb1.1k wrote:


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

ADD COMMENTlink written 8.7 years ago by Bilouweb1.1k
gravatar for Gww
8.7 years ago by
Gww2.6k wrote:

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.

ADD COMMENTlink written 8.7 years ago by Gww2.6k
Please log in to add an answer.


Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1650 users visited in the last hour