Evolutionary pressures shaping protein interaction networks are
practically unexplored, although the importance of such studies has
been recognized . The earlier studies addressing this question analyzed the conservation of network motives [2-5], or the rate of link dynamics in interaction networks [6,7]. Although the importance of different protein properties to the evolution rates of proteins has been questioned [8-10], proteins interacting with multiple partners simultaneously have been shown to have a slower pace of evolution .
Thus, the properties of interaction networks can be thought to
influence the evolution of organisms. More general knowledge about the
effectors shaping protein interaction networks would give insights on
several aspects of the formation of complex biological systems.
For detailed analysis of the evolution of a protein-protein
interaction (PPI) network it is necessary to have knowledge about the
emergence of all the proteins in the network and their interactions.
Some investigations in this line have been presented [12,13].
The problem is that the steps which lead to the current situation
cannot be directly addressed. To be able to follow the development in
biological systems, information about biological evolution should be
applied. One attempt in this direction was to use so-called isotemporal
categories to express the appearance of a gene or protein in organisms .
DNA and protein sequences hold their past in their structure, which
can be reconstructed with the standard tools of phylogenetics. Here we
performed to our knowledge the first PPI network analysis utilizing
phylogenetic information. One of the reasons for the lack of this kind
of study is the problem of obtaining accurate and validated data for a
system that covers the biological network, its gene and protein
constituents and their evolutionary history and homologs. We have
collected such data for the human immune system.
The human immune system, which is one of the most complex biological
machineries, has been widely investigated at the molecular, cellular
and organ level in its normal state and during disease. It is a very
complex system built up from several different tissues, cell types,
molecules and processes. The evolutionary history of the human immune
system is widely studied (see e.g. ), but we still need new data to complete the picture.
The Essential Human Immunome is a reference collection of genes and
proteins involved in human immunity which is distributed in the
Immunome database [16,17]. Evolutionary data for all these proteins is collected in the ImmTree database .
Experimentally verified protein-protein interaction data for the
immunome proteins was collected from the Human Protein Reference
Database (HPRD)  and used to reconstruct the protein interaction network.
Recently, several studies have been published about natural networks , ranging from social interactions [21,22] via protein-protein interactions [23,24] to the spreading of epidemics  as well as human made networks like telecommunication networks [26,27] and the Internet [28,29].
It was initially surprising that the different networks share several
common characteristics, which suggests common organizing principles for
their emergence .
Preferential attachment [31-33]
suggests that a new protein is more likely to be connected to a highly
connected protein than to a protein with fewer interactions. Networks
built up according to this principle, have been shown to have scale
free characteristics [34,35].
Scale free networks have been detected from several different sources,
but thus far it has been very rare to observe the preferential
attachment rule at work, especially in the case of protein interaction
The evolution and development of networks has been widely studied [38,39]. Many earlier reports on the evolution of protein interaction networks have focused on yeast high throughput datasets [14,40,41]. Evolutionary comparisons have been limited to a few reference genomes. The new dataset on the human immunome  related proteins and their evolution allowed us to assign evolutionary levels to the proteins .
These levels can be interpreted as indicating the steps of emergence of
proteins. Reliable protein interaction data can be assigned from HPRD,
which contains experimentally verified interactions from literature .
We studied the emergence of the immunome PPI network and elucidated
which of the network parameters are shaped by evolutionary pressures
and how these parameters have changed during time.