Parsimonious reconstruction of network evolution

Abstract. We consider the problem of reconstructing a maximally par-simonious history of network evolution under models that support gene duplication and loss and independent interaction gain and loss. We intro-duce a combinatorial framework for encoding network histories, and we give a fast procedure that, given a set of duplication histories, in practice finds network histories with close to the minimum number of interaction gain or loss events. In contrast to previous studies, our method does not require knowing the relative ordering of unrelated duplication events. Results on simulated histories suggest that common ancestral networks can be accurately reconstructed using this parsimony approach.