title: Efficient α, β-motif finder for identification of phenotype-related functional modules.
abstract: BACKGROUND
  Microbial communities in their natural environments exhibit phenotypes that can directly cause particular diseases, convert biomass or wastewater to energy, or degrade various environmental contaminants. Understanding how these communities realize specific phenotypic traits (e.g., carbon fixation, hydrogen production) is critical for addressing health, bioremediation, or bioenergy problems.
  
  
  RESULTS
  In this paper, we describe a graph-theoretical method for in silico prediction of the cellular subsystems that are related to the expression of a target phenotype. The proposed (α, β)-motif finder approach allows for identification of these phenotype-related subsystems that, in addition to metabolic subsystems, could include their regulators, sensors, transporters, and even uncharacterized proteins. By comparing dozens of genome-scale networks of functionally associated proteins, our method efficiently identifies those statistically significant functional modules that are in at least α networks of phenotype-expressing organisms but appear in no more than β networks of organisms that do not exhibit the target phenotype. It has been shown via various experiments that the enumerated modules are indeed related to phenotype-expression when tested with different target phenotypes like hydrogen production, motility, aerobic respiration, and acid-tolerance.
  
  
  CONCLUSIONS
  Thus, we have proposed a methodology that can identify potential statistically significant phenotype-related functional modules. The functional module is modeled as an (α, β)-clique, where α and β are two criteria introduced in this work. We also propose a novel network model, called the two-typed, divided network. The new network model and the criteria make the problem tractable even while very large networks are being compared. The code can be downloaded from http://www.freescience.org/cs/ABClique/
authors.affiliation: Department of Computer Science, North Carolina State University, Raleigh, NC 27695, USA.
authors.forename: Matthew C
authors.initials: MC
authors.lastname: Schmidt
authors.forename: Andrea M
authors.initials: AM
authors.lastname: Rocha
authors.forename: Kanchana
authors.initials: K
authors.lastname: Padmanabhan
authors.forename: Zhengzhang
authors.initials: Z
authors.lastname: Chen
authors.forename: Kathleen
authors.initials: K
authors.lastname: Scott
authors.forename: James R
authors.initials: JR
authors.lastname: Mihelcic
authors.forename: Nagiza F
authors.initials: NF
authors.lastname: Samatova
mesh_terms: D000143:Acids / Q000378:metabolism*; D000465:Algorithms; D001419:Bacteria / Q000235:genetics* / Q000378:metabolism*; D002952:Citric Acid Cycle; D003205:Computing Methodologies; D006859:Hydrogen / Q000378:metabolism; D010641:Phenotype; D020560:Proteobacteria
chemical_list: D000143:Acids; D006859:Hydrogen
references.citation: J Bacteriol. 2006 Sep;188(17):6143-52
references.pmid: 16923881
references.citation: Mol Syst Biol. 2006;2:2006.0005
references.pmid: 16732191
references.citation: J Bacteriol. 2002 Oct;184(19):5364-75
references.pmid: 12218023
references.citation: Nat Rev Microbiol. 2004 Nov;2(11):898-907
references.pmid: 15494746
references.citation: Bioinformatics. 2008 Apr 1;24(7):979-86
references.pmid: 18304937
references.citation: J Mol Biol. 2004 Nov 12;344(1):155-67
references.pmid: 15504408
references.citation: J Bacteriol. 1992 May;174(10):3242-9
references.pmid: 1315732
references.citation: Nucleic Acids Res. 2006 Jan 1;34(Database issue):D344-8
references.pmid: 16381883
references.citation: J Proteome Res. 2006 Apr;5(4):801-7
references.pmid: 16602686
references.citation: FEBS Lett. 2006 Jan 23;580(2):677-81
references.pmid: 16412426
references.citation: Science. 2008 Apr 25;320(5875):495-7
references.pmid: 18436781
references.citation: Metab Eng. 2010 May;12(3):268-81
references.pmid: 20060060
references.citation: Proc Natl Acad Sci U S A. 1999 Apr 13;96(8):4285-8
references.pmid: 10200254
references.citation: Nucleic Acids Res. 2009 Jan;37(Database issue):D412-6
references.pmid: 18940858
references.citation: Genes Dev. 2007 May 1;21(9):1010-24
references.pmid: 17473168
references.citation: BMC Bioinformatics. 2003 Sep 11;4:41
references.pmid: 12969510
references.citation: Appl Environ Microbiol. 2007 Mar;73(5):1665-71
references.pmid: 17220249
references.citation: Genome Inform. 2005;16(2):260-9
references.pmid: 16901108
references.citation: Nature. 2005 Feb 3;433(7025):531-7
references.pmid: 15690043
references.citation: PLoS Comput Biol. 2006 Nov 17;2(11):e159
references.pmid: 17112314
references.citation: J Mol Biol. 2007 Sep 28;372(4):1045-1054
references.pmid: 17706667
references.citation: FEMS Microbiol Rev. 2001 Aug;25(4):455-501
references.pmid: 11524134
references.citation: Mol Syst Biol. 2007;3:88
references.pmid: 17353930
references.citation: J Bacteriol. 2010 Nov;192(22):5874-80
references.pmid: 20833801
references.citation: Curr Biol. 2003 Jan 21;13(2):129-33
references.pmid: 12546786
references.citation: J Am Soc Mass Spectrom. 2005 Aug;16(8):1250-61
references.pmid: 15979332
references.citation: J Mol Evol. 2000 Jul;51(1):1-11
references.pmid: 10903367