title: Steiner tree methods for optimal sub-network identification: an empirical study.
abstract: BACKGROUND
  Analysis and interpretation of biological networks is one of the primary goals of systems biology. In this context identification of sub-networks connecting sets of seed proteins or seed genes plays a crucial role. Given that no natural node and edge weighting scheme is available retrieval of a minimum size sub-graph leads to the classical Steiner tree problem, which is known to be NP-complete. Many approximate solutions have been published and theoretically analyzed in the computer science literature, but far less is known about their practical performance in the bioinformatics field.
  
  
  RESULTS
  Here we conducted a systematic simulation study of four different approximate and one exact algorithms on a large human protein-protein interaction network with ~14,000 nodes and ~400,000 edges. Moreover, we devised an own algorithm to retrieve a sub-graph of merged Steiner trees. The application of our algorithms was demonstrated for two breast cancer signatures and a sub-network playing a role in male pattern baldness.
  
  
  CONCLUSIONS
  We found a modified version of the shortest paths based approximation algorithm by Takahashi and Matsuyama to lead to accurate solutions, while at the same time being several orders of magnitude faster than the exact approach. Our devised algorithm for merged Steiner trees, which is a further development of the Takahashi and Matsuyama algorithm, proved to be useful for small seed lists. All our implemented methods are available in the R-package SteinerNet on CRAN (http://www.r-project.org) and as a supplement to this paper.
authors.affiliation: Bonn-Aachen International Center for IT, Rheinische Friedrich-Wilhelms Universitat Bonn, Dahlmannstr 2, 53113 Bonn, Germany. sadeghi.afshin@yahoo.com
authors.forename: Afshin
authors.initials: A
authors.lastname: Sadeghi
authors.forename: Holger
authors.initials: H
authors.lastname: Fröhlich
mesh_terms: D000465:Algorithms; D000505:Alopecia / Q000378:metabolism; D001943:Breast Neoplasms / Q000175:diagnosis / Q000235:genetics; D005260:Female; D020869:Gene Expression Profiling; D053263:Gene Regulatory Networks; D006655:Histone Deacetylases / Q000378:metabolism; D006801:Humans; D008297:Male; D011379:Prognosis; D025941:Protein Interaction Mapping; D011944:Receptors, Androgen / Q000378:metabolism; D012097:Repressor Proteins / Q000378:metabolism; D049490:Systems Biology / Q000379:methods
chemical_list: D011944:Receptors, Androgen; D012097:Repressor Proteins; C486544:HDAC9 protein, human; D006655:Histone Deacetylases