title: SMETANA: accurate and scalable algorithm for probabilistic alignment of large-scale biological networks.
abstract: In this paper we introduce an efficient algorithm for alignment of multiple large-scale biological networks. In this scheme, we first compute a probabilistic similarity measure between nodes that belong to different networks using a semi-Markov random walk model. The estimated probabilities are further enhanced by incorporating the local and the cross-species network similarity information through the use of two different types of probabilistic consistency transformations. The transformed alignment probabilities are used to predict the alignment of multiple networks based on a greedy approach. We demonstrate that the proposed algorithm, called SMETANA, outperforms many state-of-the-art network alignment techniques, in terms of computational efficiency, alignment accuracy, and scalability. Our experiments show that SMETANA can easily align tens of genome-scale networks with thousands of nodes on a personal computer without any difficulty. The source code of SMETANA is available upon request. The source code of SMETANA can be downloaded from http://www.ece.tamu.edu/~bjyoon/SMETANA/.
authors.affiliation: Department of Plant and Microbial Biology, University of California, Berkely, California, USA.
authors.forename: Sayed Mohammad Ebrahim
authors.initials: SM
authors.lastname: Sahraeian
authors.forename: Byung-Jun
authors.initials: BJ
authors.lastname: Yoon
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D017124:Conserved Sequence; D030562:Databases, Protein; D011336:Probability; D060066:Protein Interaction Maps; D017386:Sequence Homology, Amino Acid; D013997:Time Factors