*Result*: Assembling networks of microbial genomes using linear programming.

Title:
Assembling networks of microbial genomes using linear programming.
Authors:
Holloway C; Faculty of Computer Science, Dalhousie University, 6050 University Avenue, Halifax, Nova Scotia B3 H 1W5, Canada., Beiko RG
Source:
BMC evolutionary biology [BMC Evol Biol] 2010 Nov 20; Vol. 10, pp. 360. Date of Electronic Publication: 2010 Nov 20.
Publication Type:
Journal Article; Validation Study
Language:
English
Journal Info:
Publisher: BioMed Central Country of Publication: England NLM ID: 100966975 Publication Model: Electronic Cited Medium: Internet ISSN: 1471-2148 (Electronic) Linking ISSN: 14712148 NLM ISO Abbreviation: BMC Evol Biol Subsets: MEDLINE
Imprint Name(s):
Original Publication: London : BioMed Central, [2001-
MeSH Terms:
Genome, Bacterial* , Programming, Linear*, Bacteria/genetics ; Computational Biology/methods ; Algorithms ; Computer Simulation ; Databases, Genetic ; Models, Genetic
References:
Proc Biol Sci. 2004 Dec 22;271(1557):2551-8. (PMID: 15615680)
Science. 1999 Jun 25;284(5423):2124-9. (PMID: 10381871)
Science. 2004 Dec 10;306(5703):1928-9. (PMID: 15591201)
Syst Biol. 2008 Dec;57(6):844-56. (PMID: 19085328)
Genome Res. 2003 Nov;13(11):2498-504. (PMID: 14597658)
Proc Natl Acad Sci U S A. 2009 Apr 7;106(14):5865-70. (PMID: 19307556)
Syst Biol. 2008 Dec;57(6):939-47. (PMID: 19085334)
Microbiol Mol Biol Rev. 2000 Mar;64(1):202-36. (PMID: 10704480)
Bioinformatics. 2009 Jun 15;25(12):i85-93. (PMID: 19478021)
Nat Genet. 2004 Jul;36(7):760-6. (PMID: 15208628)
Annu Rev Microbiol. 2001;55:709-42. (PMID: 11544372)
Mol Microbiol. 1997 Dec;26(5):1005-11. (PMID: 9426137)
Genome Res. 2005 Jul;15(7):954-9. (PMID: 15965028)
IEEE/ACM Trans Comput Biol Bioinform. 2004 Oct-Dec;1(4):151-158. (PMID: 17051697)
ISME J. 2009 Sep;3(9):1012-35. (PMID: 19404327)
Bacteriol Rev. 1970 Mar;34(1):40-81. (PMID: 4909647)
Microb Comp Genomics. 1998;3(3):177-92. (PMID: 9775388)
Proc Natl Acad Sci U S A. 2007 Jan 16;104(3):870-5. (PMID: 17213324)
Nat Genet. 2005 Dec;37(12):1372-5. (PMID: 16311593)
Methods Mol Biol. 2009;532:127-39. (PMID: 19271182)
PLoS Biol. 2005 May;3(5):e130. (PMID: 15799709)
Proc Natl Acad Sci U S A. 2005 Oct 4;102(40):14332-7. (PMID: 16176988)
Mol Biol Evol. 2008 Apr;25(4):762-77. (PMID: 18234706)
PLoS Comput Biol. 2009 Sep;5(9):e1000501. (PMID: 19749978)
Science. 2007 Sep 21;317(5845):1753-6. (PMID: 17761848)
PLoS Comput Biol. 2009 May;5(5):e1000392. (PMID: 19478997)
BMC Evol Biol. 2007 Feb 08;7 Suppl 1:S7. (PMID: 17288580)
Archaea. 2007 May;2(2):83-93. (PMID: 17350929)
Mol Biol Evol. 2006 May;23(5):1019-30. (PMID: 16495350)
BMC Bioinformatics. 2007 Nov 22;8:460. (PMID: 18034891)
Proc Natl Acad Sci U S A. 2010 Jan 5;107(1):127-32. (PMID: 20007769)
Science. 1997 Oct 24;278(5338):631-7. (PMID: 9381173)
BMC Evol Biol. 2008 Oct 03;8:272. (PMID: 18834516)
Genome Biol. 2008 Oct 13;9(10):R151. (PMID: 18851752)
J Biol. 2009;8(6):59. (PMID: 19594957)
J Bioinform Comput Biol. 2003 Apr;1(1):95-117. (PMID: 15290783)
Mol Biol Evol. 2004 Feb;21(2):255-65. (PMID: 14660700)
Trends Microbiol. 2006 Feb;14(2):64-9. (PMID: 16413191)
Genome Res. 2009 Jan;19(1):12-23. (PMID: 19047519)
Infect Genet Evol. 2009 Dec;9(6):1132-47. (PMID: 19712752)
Microbiology (Reading). 2000 Oct;146 ( Pt 10):2345-2350. (PMID: 11021911)
Science. 2006 Mar 3;311(5765):1283-7. (PMID: 16513982)
Bioinformatics. 2008 Feb 1;24(3):319-24. (PMID: 18042555)
Nature. 1980 Jan 10;283(5743):212-4. (PMID: 6243180)
Biosystems. 1993;31(2-3):111-9. (PMID: 8155843)
Bioinformatics. 2005 Feb 15;21(4):456-63. (PMID: 15608047)
Antimicrob Agents Chemother. 2009 Dec;53(12):5294-6. (PMID: 19752283)
Proc Natl Acad Sci U S A. 2005 Dec 13;102(50):18147-52. (PMID: 16330755)
Int J Syst Evol Microbiol. 2003 Mar;53(Pt 2):455-458. (PMID: 12710612)
Biol Direct. 2006 Jul 11;1:19. (PMID: 16834776)
Bioinformatics. 2007 Apr 1;23(7):825-31. (PMID: 17267425)
Science. 2009 Jun 12;324(5933):1454-7. (PMID: 19520963)
Nature. 2009 Dec 24;462(7276):1056-60. (PMID: 20033048)
Genome Biol. 2004;5(3):R17. (PMID: 15003120)
Genome Res. 2006 May;16(5):636-43. (PMID: 16651664)
Nature. 1999 May 27;399(6734):323-9. (PMID: 10360571)
J Bacteriol. 2002 Sep;184(17):4891-905. (PMID: 12169615)
Int Microbiol. 2004 Mar;7(1):41-52. (PMID: 15179606)
J Mol Evol. 2002 Mar;54(3):396-402. (PMID: 11847565)
Entry Date(s):
Date Created: 20101125 Date Completed: 20110218 Latest Revision: 20211020
Update Code:
20260130
PubMed Central ID:
PMC3224671
DOI:
10.1186/1471-2148-10-360
PMID:
21092133
Database:
MEDLINE

*Further Information*

*Background: Microbial genomes exhibit complex sets of genetic affinities due to lateral genetic transfer. Assessing the relative contributions of parent-to-offspring inheritance and gene sharing is a vital step in understanding the evolutionary origins and modern-day function of an organism, but recovering and showing these relationships is a challenging problem.
Results: We have developed a new approach that uses linear programming to find between-genome relationships, by treating tables of genetic affinities (here, represented by transformed BLAST e-values) as an optimization problem. Validation trials on simulated data demonstrate the effectiveness of the approach in recovering and representing vertical and lateral relationships among genomes. Application of the technique to a set comprising Aquifex aeolicus and 75 other thermophiles showed an important role for large genomes as 'hubs' in the gene sharing network, and suggested that genes are preferentially shared between organisms with similar optimal growth temperatures. We were also able to discover distinct and common genetic contributors to each sequenced representative of genus Pseudomonas.
Conclusions: The linear programming approach we have developed can serve as an effective inference tool in its own right, and can be an efficient first step in a more-intensive phylogenomic analysis.*