Bioinformatics And Graph Algorithms
5
13
Entering edit mode
14.2 years ago
Lissa ▴ 80

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

graph algorithm • 9.2k views
ADD COMMENT
16
Entering edit mode
14.2 years ago

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 COMMENT
5
Entering edit mode
14.2 years ago
Bilouweb ★ 1.1k

Hello.

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

ADD COMMENT
4
Entering edit mode
14.2 years ago

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 COMMENT
3
Entering edit mode
14.2 years ago
Gww ★ 2.7k

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 COMMENT

Login before adding your answer.

Traffic: 2668 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6