MOTIVATION: Recent technological advances in measuring molecular interactions have resulted in an increasing number of large-scale biological networks. Translation of these enormous network data into meaningful biological insights requires efficient computational techniques that can unearth the biological information that is encoded in the networks. One such example is network querying, which aims to identify similar subnetwork regions in a large target network that are similar to a given query network. Network querying tools can be used to identify novel biological pathways that are homologous to known pathways, thereby enabling knowledge transfer across different organisms. RESULTS: In this article, we introduce an efficient algorithm for querying large-scale biological networks, called RESQUE. The proposed algorithm adopts a semi-Markov random walk (SMRW) model to probabilistically estimate the correspondence scores between nodes that belong to different networks. The target network is iteratively reduced based on the estimated correspondence scores, which are also iteratively re-estimated to improve accuracy until the best matching subnetwork emerges. We demonstrate that the proposed network querying scheme is computationally efficient, can handle any network query with an arbitrary topology and yields accurate querying results. AVAILABILITY: The source code of RESQUE is freely available at http://www.ece.tamu.edu/~bjyoon/RESQUE/

Network querying aims to search a large network for subnetwork regions that are similar to a given query network. In this paper, we propose a novel algorithm for querying large scale protein interaction networks. In this algorithm, we iteratively compute the correspondence scores between nodes in the query and the target networks using semi-Markov random walk. Based on these scores, we reduce the search space in the target network by discarding irrelevant nodes. The scores are re-estimated in each iteration after removing such nodes, which ultimately leads to more accurate querying result. Numerical experiments based on both synthetic and real networks show that the algorithm can efficiently find accurate querying results.

BACKGROUND: Comparative network analysis aims to identify common subnetworks in biological networks. It can facilitate the prediction of conserved functional modules across different species and provide deep insights into their underlying regulatory mechanisms. Recently, it has been shown that hidden Markov models (HMMs) can provide a flexible and computationally efficient framework for modeling and comparing biological networks. RESULTS: In this work, we show that using global correspondence scores between molecules can improve the accuracy of the HMM-based network alignment results. The global correspondence scores are computed by performing a semi-Markov random walk on the networks to be compared. The resulting score naturally integrates the sequence similarity between molecules and the topological similarity between their molecular interactions, thereby providing a more effective measure for estimating the functional similarity between molecules. By incorporating the global correspondence scores, instead of relying on sequence similarity or functional annotation scores used by previous approaches, our HMM-based network alignment method can identify conserved subnetworks that are functionally more coherent. CONCLUSIONS: Performance analysis based on synthetic and microbial networks demonstrates that the proposed network alignment strategy significantly improves the robustness and specificity of the predicted alignment results, in terms of conserved functional similarity measured based on KEGG ortholog (KO) groups. These results clearly show that the HMM-based network alignment framework using global correspondence scores can effectively find conserved biological pathways and has the potential to be used for automatic functional annotation of biomolecules.

BACKGROUND: Accurate and efficient structural alignment of non-coding RNAs (ncRNAs) has grasped more and more attentions as recent studies unveiled the significance of ncRNAs in living organisms. While the Sankoff style structural alignment algorithms cannot efficiently serve for multiple sequences, mostly progressive schemes are used to reduce the complexity. However, this idea tends to propagate the early stage errors throughout the entire process, thereby degrading the quality of the final alignment. For multiple protein sequence alignment, we have recently proposed PicXAA which constructs an accurate alignment in a non-progressive fashion. RESULTS: Here, we propose PicXAA-R as an extension to PicXAA for greedy structural alignment of ncRNAs. PicXAA-R efficiently grasps both folding information within each sequence and local similarities between sequences. It uses a set of probabilistic consistency transformations to improve the posterior base-pairing and base alignment probabilities using the information of all sequences in the alignment. Using a graph-based scheme, we greedily build up the structural alignment from sequence regions with high base-pairing and base alignment probabilities. CONCLUSIONS: Several experiments on datasets with different characteristics confirm that PicXAA-R is one of the fastest algorithms for structural alignment of multiple RNAs and it consistently yields accurate alignment results, especially for datasets with locally similar sequences. PicXAA-R source code is freely available at: http://www.ece.tamu.edu/~bjyoon/picxaa/.

In this letter, we propose a novel similarity measure for comparing Hidden Markov models (HMMs) and an efficient scheme for its computation. In the proposed approach, we probabilistically evaluate the correspondence, or goodness of match, between every pair of states in the respective HMMs, based on the concept of semi-Markov random walk. We show that this correspondence score reflects the contribution of a given state pair to the overall similarity between the two HMMs. For similar HMMs, each state in one HMM is expected to have only a few matching states in the other HMM, resulting in a sparse state correspondence score matrix. This allows us to measure the similarity between HMMs by evaluating the sparsity of the state correspondence matrix. Estimation of the proposed similarity score does not require time-consuming Monte-Carlo simulations, hence it can be computed much more efficiently compared to the Kullback–Leibler divergence (KLD) thas has been widely used. We demonstrate the effectiveness of the proposed measure through several examples.

This paper presents a robust image watermarking scheme based on a sample projection approach. While we consider the human visual system in our watermarking algorithm, we use the low-frequency components of image blocks for data hiding to obtain high robustness against attacks. We use four samples of the approximation coefficients of the image blocks to construct a line segment in the 2-D space. The slope of this line segment, which is invariant to the gain factor, is employed for watermarking purpose. We embed the watermarking code by projecting the line segment on some specific lines according to message bits. To design a maximum likelihood decoder, we compute the distribution of the slope of the embedding line segment for Gaussian samples. The performance of the proposed technique is analytically investigated and verified via several simulations. Experimental results confirm the validity of our model and its high robustness against common attacks in comparison with similar watermarking techniques that are invariant to the gain attack.

In this paper, an improved multiplicative image watermarking system is presented. Since human visual system is less sensitive to the image edges, watermarking is applied in the contourlet domain, which represents image edges sparsely. In the presented scheme, watermark data is embedded in directional subband with the highest energy. By modeling the contourlet coefficients with General Gaussian Distribution (GGD), the distribution of watermarked noisy coefficients is analytically calculated. The tradeoff between the transparency and robustness of the watermark data is solved in a novel fashion. At the receiver, based on the Maximum Likelihood (ML) decision rule, an optimal detector by the aid of channel side information is proposed. In the next step, a blind extension of the suggested algorithm is presented using the patchwork idea. Experimental results confirm the superiority of the proposed method against common attacks, such as Additive White Gaussian Noise (AWGN), JPEG compression, and rotation attacks, in comparison with the recently proposed techniques.

In this paper, a novel scaling based information hiding approach robust against noise and gain attack is presented. The host signal is assumed to be stationary Gaussian modeled with a first-order autoregressive process. For data embedding, the host signal is divided into two parts. One part is manipulated while the other part is kept unchanged for parameter estimation. The decoding scheme using the ratio of samples is suitable for highly correlated signals in which the decoding process is difficult. By calculating the distribution of the ratio, the performance of the maximum likelihood decoder is analytically studied. The proposed algorithm is applied to several artificial Gaussian autoregressive signals to verify the validity of our results.

In this paper, a new blind scaling based watermarking approach is presented. The host signal is assumed to be stationary Gaussian with first-order autoregressive model. Partitioning the host signal into two separate parts, the data is embedded in one part and the other is kept unchanged for blind parameter estimation. Driving the distribution of the decision variable we have suggested a maximum likelihood decoding algorithm which is independent of the host signal distribution and can be applied for any transform domains. The proposed algorithm is applied to both artificial Gaussian autoregressive signals as well as various test images. Experimental results confirm the independence of the decoder performance to the host signal distribution and its great robustness against common attacks.

In this paper, a new scaling-based image-adaptive watermarking system has been presented, which exploits human visual model for adapting the watermark data to local properties of the host image. Its improved robustness is due to embedding in the low-frequency wavelet coefficients and optimal control of its strength factor from HVS point of view. Maximum likelihood (ML) decoder is used aided by the channel side information. The performance of the proposed scheme is analytically calculated and verified by simulation. Experimental results confirm the imperceptibility of the proposed method and its higher robustness against attacks compared to alternative watermarking methods in the literature.

In this paper, a new multiplicative image watermarking system is presented. As human visual system is less sensitive to the image edges, watermarking is applied in the contourlet domain, which represents image edges sparsely. In the presented scheme, watermark data is embedded in the most energetic directional subband. By modeling general gaussian distribution (GGD) for the contourlet coefficients, the distribution of watermarked noisy coefficients is analytically calculated. At the receiver, based on the maximum likelihood (ML) decision rule, the optimal detector is proposed. Experimental results show the imperceptibility and high robustness of the proposed method against Additive White Gaussian Noise (AWGN) and JPEG compression attacks.

In this paper we propose a new method for image noise reduction based on wavelet transform. In this method we introduce an improved version of thresholding neural networks (TNN) by utilizing a new class of smooth nonlinear thresholding functions as the activation function. Using this approach we will find the best thresholds in the sense of minimum mean square error (MMSE). Then using TNN with obtained thresholds, we employ a cycle-spinning-based technique to reduce image artifacts. Experimental results indicate that the proposed method outperforms several other established wavelet denoising techniques, in terms of peak-signal-to-noise-ratio (PSNR) and visual quality.