Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2011 Oct 24:5:172.
doi: 10.1186/1752-0509-5-172.

DENSE: efficient and prior knowledge-driven discovery of phenotype-associated protein functional modules

Willam Hendrix  1 , Andrea M Rocha, Kanchana Padmanabhan, Alok Choudhary, Kathleen Scott, James R Mihelcic, Nagiza F Samatova
Affiliations

DENSE: efficient and prior knowledge-driven discovery of phenotype-associated protein functional modules

Willam Hendrix et al. BMC Syst Biol. .

Abstract

Background: Identifying cellular subsystems that are involved in the expression of a target phenotype has been a very active research area for the past several years. In this paper, cellular subsystem refers to a group of genes (or proteins) that interact and carry out a common function in the cell. Most studies identify genes associated with a phenotype on the basis of some statistical bias, others have extended these statistical methods to analyze functional modules and biological pathways for phenotype-relatedness. However, a biologist might often have a specific question in mind while performing such analysis and most of the resulting subsystems obtained by the existing methods might be largely irrelevant to the question in hand. Arguably, it would be valuable to incorporate biologist's knowledge about the phenotype into the algorithm. This way, it is anticipated that the resulting subsytems would not only be related to the target phenotype but also contain information that the biologist is likely to be interested in.

Results: In this paper we introduce a fast and theoretically guranteed method called DENSE (Dense and ENriched Subgraph Enumeration) that can take in as input a biologist's prior knowledge as a set of query proteins and identify all the dense functional modules in a biological network that contain some part of the query vertices. The density (in terms of the number of network egdes) and the enrichment (the number of query proteins in the resulting functional module) can be manipulated via two parameters γ and μ, respectively.

Conclusion: This algorithm has been applied to the protein functional association network of Clostridium acetobutylicum ATCC 824, a hydrogen producing, acid-tolerant organism. The algorithm was able to verify relationships known to exist in literature and also some previously unknown relationships including those with regulatory and signaling functions. Additionally, we were also able to hypothesize that some uncharacterized proteins are likely associated with the target phenotype. The DENSE code can be downloaded from http://www.freescience.org/cs/DENSE/

PubMed Disclaimer

Figures

Figure 1
Figure 1
DENSE cluster containing hydrogenase and associated proteins identified by DENSE.
Figure 2
Figure 2
DENSE cluster containing phosophoheptose and interacting proteins identified by DENSE algorithm.
Figure 3
Figure 3
DENSE cluster containing pyruvate-ferredoxin oxidoreductase and interacting proteins identified by DENSE algorithm.
Figure 4
Figure 4
DENSE cluster containing butyrate kinase enzymes and phosphate butyryltransferase identified by DENSE.
Figure 5
Figure 5
DENSE cluster containing phosphotransferase system (PTS) enzymes identified by DENSE algorithm.
Figure 6
Figure 6
Timing results for μ, γ-quasi-clique enumeration algorithm. Time is reported in milliseconds per quasi-clique. Descriptions of the various quasi-cliques can be found in Table 6, and descriptions of the graphs used can be found in Table 7.
Figure 7
Figure 7
Speedup results for using hierarchical bitmap index in μ, γ-quasi-clique enumeration algorithm. Speedup is reported in percentage; i.e., a value of 100% indicates that using the hierarchical bitmap index was twice as fast as the implementation with the flat index, and a value of -100% indicates that using the flat bitmap index was twice as fast as the implementation with the hierarchical index.
Figure 8
Figure 8
Overview of the DENSE algorithm.
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

References

    1. Lopez-Gomollon S, Hernandez JA, Pellicer S, Angarica VE, Peleato ML, Fillat MF. Cross-talk between iron and nitrogen regulatory networks in Anabaena (Nostoc) sp. PCC 7120: Identification of overlapping genes in FurA and NtcA regulons. J Mol Biol. 2007;374:267–281. doi: 10.1016/j.jmb.2007.09.010. - DOI - PubMed
    1. Yebra MJ, Perez-Martinez G. Cross-talk between the L-sorbose and D-sorbitol (D-glucitol) metabolic pathways in Lactobacillus casei. Microbiology. 2002;148(8):2351–2359. - PubMed
    1. Jensen LJ, Kuhn M, Stark M, Chaffron S, Creevey C, Muller J, Doerks T, Julien P, Roth A, Simonovic M, Bork P, von Mering C. STRING 8-a global view on proteins and their functional interactions in 630 organisms. Nucl Acids Res. 2009;37(suppl_1):D412–416. - PMC - PubMed
    1. Zhang H, Bruns MA, Logan BE. Biological hydrogen production by Clostridium acetobutylicum in an unsaturated flow reactor. Water Res. 2006;40(4):728–734. doi: 10.1016/j.watres.2005.11.041. - DOI - PubMed
    1. Huang Y, Zong W, Yang X, Wang R, Hemme CL, Zhou J, Zhou Z. Succesion of the bacterial community and dynamics of hydrogen producers in a hydrogen-producing bioreactor. Appl Environ Microbiol. 2010;76(10):3387–3390. doi: 10.1128/AEM.02444-09. - DOI - PMC - PubMed

Publication types

MeSH terms

Substances