  Complexes of physically interacting proteins are one of the fundamental
functional units responsible for driving key biological mechanisms within the
cell. Their identification is therefore necessary not only to understand
complex formation but also the higher level organization of the cell. With the
advent of high-throughput techniques in molecular biology, significant amount
of physical interaction data has been cataloged from organisms such as yeast,
which has in turn fueled computational approaches to systematically mine
complexes from the network of physical interactions among proteins (PPI
network). In this survey, we review, classify and evaluate some of the key
computational methods developed till date for the identification of protein
complexes from PPI networks. We present two insightful taxonomies that reflect
how these methods have evolved over the years towards improving automated
complex prediction. We also discuss some open challenges facing accurate
reconstruction of complexes, the crucial ones being presence of high proportion
of errors and noise in current high-throughput datasets and some key aspects
overlooked by current complex detection methods. We hope this review will not
only help to condense the history of computational complex detection for easy
reference, but also provide valuable insights to drive further research in this
area.
