Parsimonious reconstruction of network evolution
Patro et al. Algorithms for Molecular Biology 2012, 7:25
MetadataShow full item record
Background: Understanding the evolution of biological networks can provide insight into how their modular structure arises and how they are aﬀected by environmental changes. One approach to studying the evolution of these networks is to reconstruct plausible common ancestors of present-day networks, allowing us to analyze how the topological properties change over time and to posit mechanisms that drive the networks’ evolution. Further, putative ancestral networks can be used to help solve other diﬃcult problems in computational biology, such as network alignment. Results: We introduce a combinatorial framework for encoding network histories, and we give a fast procedure that, given a set of gene duplication histories, in practice ﬁnds network histories with close to the minimum number of interaction gain or loss events to explain the observed present-day networks. In contrast to previous studies, our method does not require knowing the relative ordering of unrelated duplication events. Results on simulated histories and real biological networks both suggest that common ancestral networks can be accurately reconstructed using this parsimony approach. A software package implementing our method is available under the Apache 2.0 license at http://cbcb.umd.edu/kingsford-group/parana. Conclusions: Our parsimony-based approach to ancestral network reconstruction is both eﬃcient and accurate. We show that considering a larger set of potential ancestral interactions by not assuming a relative ordering of unrelated duplication events can lead to improved ancestral network inference.
Showing items related by title, author, creator and subject.
Optimization of Contemporary Telecommunications Networks: Generalized Spanning Trees and WDM Optical Networks Stanojevic, Daliborka (2005-12-05)We present a study of two NP-hard telecommunications network design problems - the prize-collecting generalized minimum spanning tree problem (PCGMST) and the design of optical networks with wavelength division ...
Fard, Pedram J. (2007-08-28)Dynamic reconfiguration of the logical topology of a network is generally used to adjust the shape of the network to adhere to changes in traffic. In this thesis the logical topology reconfiguration problem for a WDM network ...
Improving Network Performance, Security and Robustness in Hybrid Wireless Networks Using a Satellite Overlay Roy-Chowdhury, Ayan (2008-11-24)In this thesis we propose that the addition of a satellite overlay to large or dense wireless networks will result in improvement in application performance and network reliability, and also enable efficient security ...