Physical Sciences and Mathematics Commons^™

Rechecking The Centrality-Lethality Rule In The Scope Of Protein Subcellular Localization Interaction Networks, Xiaoqing Peng, Jianxin Wang, Jun Wang, Fangxiang Wu, Yi Pan

Computer Science Faculty Publications

Essential proteins are indispensable for living organisms to maintain life activities and play important roles in the studies of pathology, synthetic biology, and drug design. Therefore, besides experiment methods, many computational methods are proposed to identify essential proteins. Based on the centrality-lethality rule, various centrality methods are employed to predict essential proteins in a Protein-protein Interaction Network (PIN). However, neglecting the temporal and spatial features of protein-protein interactions, the centrality scores calculated by centrality methods are not effective enough for measuring the essentiality of proteins in a PIN. Moreover, many methods, which overfit with the features of essential proteins for …

Distributed Power-Line Outage Detection Based On Wide Area Measurement System, Liang Zhao, Wen-Zhan Song

Computer Science Faculty Publications

In modern power grids, the fast and reliable detection of power-line outages is an important functionality, which prevents cascading failures and facilitates an accurate state estimation to monitor the real-time conditions of the grids. However, most of the existing approaches for outage detection suffer from two drawbacks, namely: (i) high computational complexity; and (ii) relying on a centralized means of implementation. The high computational complexity limits the practical usage of outage detection only for the case of single-line or double-line outages. Meanwhile, the centralized means of implementation raises security and privacy issues. Considering these drawbacks, the present paper proposes a …

Accurate Viral Population Assembly From Ultra-Deep Sequencing Data, Serghei Mangul, Nicholas C. Wu, Nicholas Mancuso, Alexander Zelikovskiy, Ren Sun, Eleazar Eskin

Computer Science Faculty Publications

Motivation: Next-generation sequencing technologies sequence viruses with ultra-deep coverage, thus promising to revolutionize our understanding of the underlying diversity of viral populations. While the sequencing coverage is high enough that even rare viral variants are sequenced, the presence of sequencing errors makes it difficult to distinguish between rare variants and sequencing errors. Results: In this article, we present a method to overcome the limitations of sequencing technologies and assemble a diverse viral population that allows for the detection of previously undiscovered rare variants. The proposed method consists of a high-fidelity sequencing protocol and an accurate viral population assembly method, referred …

Cloud Computing For Detecting High-Order Genome-Wide Epistatic Interaction Via Dynamic Clustering, Xuan Guo, Yu Meng, Ning Yu, Yi Pan

Computer Science Faculty Publications

Backgroud: Taking the advan tage of high-throughput single nucleotide polymorphism (SNP) genotyping technology, large genome-wide association studies (GWASs) have been considered to hold promise for unravelling complex relationships between genotype and phenotype. At present, traditional single-locus-based methods are insufficient to detect interactions consisting of multiple-locus, which are broadly existing in complex traits. In addition, statistic tests for high order epistatic interactions with more than 2 SNPs propose computational and analytical challenges because the computation increases exponentially as the cardinality of SNPs combinations gets larger. Results: In this paper, we provide a simple, fast and powerful method using dynamic clustering and …

Identifying Dynamic Protein Complexes Based On Gene Expression Profiles And Ppi Networks, Min Li, Weijie Chen, Jianxin Wang, Fang-Xiang Wu, Yi Pan

Computer Science Faculty Publications

Identification of protein complexes fromprotein-protein interaction networks has become a key problem for understanding cellular life in postgenomic era. Many computational methods have been proposed for identifying protein complexes. Up to now, the existing computational methods are mostly applied on static PPI networks. However, proteins and their interactions are dynamic in reality. Identifying dynamic protein complexes is more meaningful and challenging. In this paper, a novel algorithm, named DPC, is proposed to identify dynamic protein complexes by integrating PPI data and gene expression profiles. According to Core-Attachment assumption, these proteins which are always active in the molecular cycle are regarded …

A Novel Algorithm For Detecting Protein Complexes With The Breadth First Search, Xiwei Tang, Jianxin Wang, Min Li, Yiming He, Yi Pan

Computer Science Faculty Publications

Most biological processes are carried out by protein complexes. A substantial number of false positives of the protein-protein interaction (PPI) data can compromise the utility of the datasets for complexes reconstruction. In order to reduce the impact of such discrepancies, a number of data integration and affinity scoring schemes have been devised. The methods encode the reliabilities (confidence) of physical interactions between pairs of proteins. The challenge now is to identify novel and meaningful protein complexes fromthe weighted PPI network. To address this problem, a novel protein complex mining algorithm ClusterBFS (Cluster with Breadth-First Search) is proposed. Based on the …

A New Essential Protein Discovery Method Based On The Integration Of Protein-Protein Interaction And Gene Expression Data, Min Li, Hanhui Zhang, Jian-Xin Wang, Yi Pan

Computer Science Faculty Publications

The article offers information on a study conducted on the essential protein discovery method, PeC, which is based on the integration of protein-protein interaction and gene expression data. It states that PeC was developed on the basis of the definitions of edge clustering coefficient (ECC) and Pearson's correlation coefficient (PCC). It mentions that a list of essential proteins of Saccharomyces cerevisiae were collected.

Background: Identification of essential proteins is always a challenging task since it requires experimental approaches that are time-consuming and laborious. With the advances in high throughput technologies, a large number of protein-protein interactions are available, which have …

Towards The Identification Of Protein Complexes And Functional Modules By Integrating Ppi Network And Gene Expression Data, Min Li, Xuehong Wu, Jianxin Wang, Yi Pan

Computer Science Faculty Publications

Background: Identification of protein complexes and functional modules from protein-protein interaction (PPI) networks is crucial to understanding the principles of cellular organization and predicting protein functions. In the past few years, many computational methods have been proposed. However, most of them considered the PPI networks as static graphs and overlooked the dynamics inherent within these networks. Moreover, few of them can distinguish between protein complexes and functional modules.

Results: In this paper, a new framework is proposed to distinguish between protein complexes and functional modules by integrating gene expression data into protein-protein interaction (PPI) data. A series of time-sequenced subnetworks …

Iteration Method For Predicting Essential Proteins Based On Orthology And Protein-Protein Interaction Networks, Wei Peng, Jianxin Wang, Weiping Wang, Qing Liu, Fang-Xiang Wu, Yi Pan

Computer Science Faculty Publications

Background: Identification of essential proteins plays a significant role in understanding minimal requirements for the cellular survival and development. Many computational methods have been proposed for predicting essential proteins by using the topological features of protein-protein interaction (PPI) networks. However, most of these methods ignored intrinsic biological meaning of proteins. Moreover, PPI data contains many false positives and false negatives. To overcome these limitations, recently many research groups have started to focus on identification of essential proteins by integrating PPI networks with other biological information. However, none of their methods has widely been acknowledged.

Results: By considering the facts that …

Trip: A Method For Novel Transcript Reconstruction From Paired-End Rna-Seq Reads, Serghei Mangul, Adrian Caciula, Dumitru Brinza, Ion I. Măndoiu, Alexander Zelikovskiy

Computer Science Faculty Publications

Preliminary experimental results on synthetic datasets generated with various sequencing parameters and distribution assumptions show that TRIP has increased transcriptome reconstruction accuracy compared to previous methods that ignore fragment length distribution information.

Guest Editors' Introduction, Jianer Chen, Ion Măndoiu, Raj Sunderraman, Jianxin Wang, Alexander Zelikovskiy

Computer Science Faculty Publications

This Supplement includes a selection of papers presented at the 7th International Symposium on Bioinformatics Research and Application (ISBRA), which was held on May 27-29, 2011 at Central South University in Changsha, China. The technical program of the symposium included 36 extended abstracts presented orally and published in volume 6674 of Springer Verlag’s Lecture Notes in Bioinformatics series. Additionally, the program included 38 short abstracts presented either orally or as posters. Authors of both extended and short abstracts presented at the symposium were invited to submit full versions of their work to this Supplement. Following a rigorous review process, 19 …

Efficient Error Correction For Next-Generation Sequencing Of Viral Amplicons, Pavel Skums, Zoya Dimitrova, David S. Campo, Gilberto Vaughan, Livia Rossi, Joseph C. Forbi, Jonny Yokosawa, Alexander Zelikovskiy, Yury Khudyakov

Computer Science Faculty Publications

Background: Next-generation sequencing allows the analysis of an unprecedented number of viral sequence variants from infected patients, presenting a novel opportunity for understanding virus evolution, drug resistance and immune escape. However, sequencing in bulk is error prone. Thus, the generated data require error identification and correction. Most error-correction methods to date are not optimized for amplicon analysis and assume that the error rate is randomly distributed. Recent quality assessment of amplicon sequences obtained using 454-sequencing showed that the error rate is strongly linked to the presence and size of homopolymers, position in the sequence and length of the amplicon. All …

Integration Of Breast Cancer Gene Signatures Based On Graph Centrality, Jianxin Wang, Gang Chen, Min Li, Yi Pan

Computer Science Faculty Publications

Background: Various gene-expression signatures for breast cancer are available for the prediction of clinical outcome. However due to small overlap between different signatures, it is challenging to integrate existing disjoint signatures to provide a unified insight on the association between gene expression and clinical outcome.

Results: In this paper, we propose a method to integrate different breast cancer gene signatures by using graph centrality in a context-constrained protein interaction network (PIN). The context-constrained PIN for breast cancer is built by integrating complete PIN and various gene signatures reported in literatures. Then, we use graph centralities to quantify the importance of …

Biological Network Motif Detection And Evaluation, Wooyoung Kim, Min Li, Jianxin Wang, Yi Pan

Computer Science Faculty Publications

Background: Molecular level of biological data can be constructed into system level of data as biological networks. Network motifs are defined as over- represented small connected subgraphs in networks and they have been used for many biological applications. Since network motif discovery involves computationally challenging processes, previous algorithms have focused on computational efficiency. However, we believe that the biological quality of network motifs is also very important.

Results: We define biological network motifs as biologically significant subgraphs and traditional network motifs are differentiated as structural network motifs in this paper. We develop five algorithms, namely, EDGEGO-BNM, EDGEBETWEENNESS-BNM, NMF-BNM, NMFGO-BNM and …

Parallel Progressive Multiple Sequence Alignment On Reconfigurable Meshes, Ken Nguyen, Yi Pan, Ge Nong

Computer Science Faculty Publications

Background: One of the most fundamental and challenging tasks in bio-informatics is to identify related sequences and their hidden biological significance. The most popular and proven best practice method to accomplish this task is aligning multiple sequences together. However, multiple sequence alignment is a computing extensive task. In addition, the advancement in DNA/RNA and Protein sequencing techniques has created a vast amount of sequences to be analyzed that exceeding the capability of traditional computing models. Therefore, an effective parallel multiple sequence alignment model capable of resolving these issues is in a great demand.

Results: We design O(1) run-time solutions …

A Comparison Of The Functional Modules Identified From Time Course And Static Ppi Network Data, Xiwei Tang, Jianxin Wang, Binbin Liu, Min Li, Gang Chen, Yi Pan

Computer Science Faculty Publications

Background: Cellular systems are highly dynamic and responsive to cues from the environment. Cellular function and response patterns to external stimuli are regulated by biological networks. A protein-protein interaction (PPI) network with static connectivity is dynamic in the sense that the nodes implement so-called functional activities that evolve in time. The shift from static to dynamic network analysis is essential for further understanding of molecular systems.

Results: In this paper, Time Course Protein Interaction Networks (TC- PINs) are reconstructed by incorporating time series gene expression into PPI networks. Then, a clustering algorithm is used to create functional modules from three …

Inferring Viral Quasispecies Spectra From 454 Pyrosequencing Reads, Irina Astrovskaya, Bassam Tork, Serghei Mangul, Kelly Westbrooks, Ion Măndoiu, Peter Balfe, Alexander Zelikovskiy

Computer Science Faculty Publications

Background: RNA viruses infecting a host usually exist as a set of closely related sequences, referred to as quasispecies. The genomic diversity of viral quasispecies is a subject of great interest, particularly for chronic infections, since it can lead to resistance to existing therapies. High-throughput sequencing is a promising approach to characterizing viral diversity, but unfortunately standard assembly software was originally designed for single genome assembly and cannot be used to simultaneously assemble and estimate the abundance of multiple closely related quasispecies sequences.

Results: In this paper, we introduce a new Viral Spectrum Assembler (ViSpA) method for quasispecies spectrum reconstruction …

Estimation Of Alternative Splicing Isoform Frequencies From Rna-Seq Data, Marius Nicolae, Serghei Mangul, Ion I. Măndoiu, Alexander Zelikovskiy

Computer Science Faculty Publications

Background: Massively parallel whole transcriptome sequencing, commonly referred as RNA-Seq, is quickly becoming the technology of choice for gene expression profiling. However, due to the short read length delivered by current sequencing technologies, estimation of expression levels for alternative splicing gene isoforms remains challenging.

Results: In this paper we present a novel expectation-maximization algorithm for inference of isoform- and genespecific expression levels from RNA-Seq data. Our algorithm, referred to as IsoEM, is based on disambiguating information provided by the distribution of insert sizes generated during sequencing library preparation, and takes advantage of base quality scores, strand and read pairing information …

Neuronbank: A Tool For Cataloging Neuronal Circuitry, Paul S. Katz, Robert Calin-Jageman, Akshaye Dhawan, Chad Frederick, Shuman Guo, Rasanjalee Dissanayaka, Naveen Hiremath, Wenjun Ma, Xiuyn Shen, Hsui C. Wang, Hong Yang, Sushil Prasad, Rajshekhar Sunderraman, Ying Zhu

Computer Science Faculty Publications

The basic unit of any nervous system is the neuron. Therefore, understanding the operation of nervous systems ultimately requires an inventory of their constituent neurons and synaptic connectivity, which form neural circuits. The presence of uniquely identifi able neurons or classes of neurons in many invertebrates has facilitated the construction of cellular-level connectivity diagrams that can be generalized across individuals within a species. Homologous neurons can also be recognized across species. Here we describe NeuronBank.org, a web-based tool that we are developing for cataloging, searching, and analyzing neuronal circuitry within and across species. Information from a single species is represented …

Identifying Protein Complexes From Interaction Networks Based On Clique Percolation And Distance Restriction, Jianxin Wang, Binbin Liu, Min Li, Yi Pan

Computer Science Faculty Publications

Background: Identification of protein complexes in large interaction networks is crucial to understand principles of cellular organization and predict protein functions, which is one of the most important issues in the post-genomic era. Each protein might be subordinate multiple protein complexes in the real protein-protein interaction networks.Identifying overlapping protein complexes from protein-protein interaction networks is a considerable research topic.

Result: As an effective algorithm in identifying overlapping module structures, clique percolation method (CPM) has a wide range of application in social networks and biological networks. However, the recognition accuracy of algorithm CPM is lowly. Furthermore, algorithm CPM is unfit to …

Recent Advances In Clustering Methods For Protein Interaction Networks, Jianxin Wang, Min Li, Youping Deng, Yi Pan

Computer Science Faculty Publications

The increasing availability of large-scale protein-protein interaction data has made it possible to understand the basic components and organization of cell machinery from the network level. The arising challenge is how to analyze such complex interacting data to reveal the principles of cellular organization, processes and functions. Many studies have shown that clustering protein interaction network is an effective approach for identifying protein complexes or functional modules, which has become a major research topic in systems biology. In this review, recent advances in clustering methods for protein interaction networks will be presented in detail. The predictions of protein functions and …

The Effect Of Wavelet Families On Watermarking, Evelyn Brannock, Michael Weeks, Robert W. Harrison

Computer Science Faculty Publications

With the advance of technologies such as the Internet, Wi-Fi Internet availability and mobile access, it is becoming harder than ever to safeguard intellectual property in a digital form. Digital watermarking is a steganographic technique that is used to protect creative content. Copyrighted work can be accessed from many different computing platforms; the same image can exist on a handheld personal digital assistant, as well as a laptop and desktop server computer. For those who want to pirate, it is simple to copy, modify and redistribute digital media. Because this impacts business profits adversely, this is a highly researched field …

Slc30a3 (Znt3) Oligomerization By Dityrosine Bonds Regulates Its Subcellular Localization And Metal Transport Capacity, Gloria Salazar, Juan M. Falcon-Perez, Robert W. Harrison, Victor Faundez

Computer Science Faculty Publications

Non-covalent and covalent homo-oligomerization of membrane proteins regulates their subcellular localization and function. Here, we described a novel oligomerization mechanism affecting solute carrier family 30 member 3/zinc transporter 3 (SLC30A3/ZnT3). Oligomerization was mediated by intermolecular covalent dityrosine bonds. Using mutagenized ZnT3 expressed in PC12 cells, we identified two critical tyrosine residues necessary for dityrosine-mediated ZnT3 oligomerization. ZnT3 carrying the Y372F mutation prevented ZnT3 oligomerization, decreased ZnT3 targeting to synaptic-like microvesicles (SLMVs), and decreased resistance to zinc toxicity. Strikingly, ZnT3 harboring the Y357F mutation behaved as a ‘‘gain-of-function’’ mutant as it displayed increased ZnT3 oligomerization, targeting to SLMVs, and increased resistance …

Association Testing By Haplotype-Sharing Methods Applicable To Whole-Genome Analysis, Ilja M. Nolte, Andre R. De Vries, Geert T. Sijker, Ritsert C. Jansen, Dumitru Brinza, Alexander Zelikovskiy, Gerard J. Te Meerman

Computer Science Faculty Publications

We propose two new haplotype-sharing methods for identifying disease loci: the haplotype sharing statistic (HSS), which compares length of shared haplotypes between cases and controls, and the CROSS test, which tests whether a case and a control haplotype show less sharing than two random haplotypes. The significance of the HSS is determined using a variance estimate from the theory of U-statistics, whereas the significance of the CROSS test is estimated from a sequential randomization procedure. Both methods are fast and hence practical, even for whole-genome screens with high marker densities. We analyzed data sets of Problems 2 and 3 of …

An Improved Ant Colony Algorithm With Diversified Solutions Based On The Immune Strategy, Ling Qin, Yi Pan, Ling Chen, Yixin Chen

Computer Science Faculty Publications

Background: Ant colony algorithm has emerged recently as a new meta- heuristic method, which is inspired from the behaviours of real ants for solving NP-hard problems. However, the classical ant colony algorithm also has its defects of stagnation and premature. This paper aims at remedying these problems.

Results: In this paper, we propose an adaptive ant colony algorithm that simulates the behaviour of biological immune system. The solutions of the problem are much more diversified than traditional ant colony algorithms.

Conclusion: The proposed method for improving the performance of traditional ant colony algorithm takes into account the polarization of the …

A Novel Approach To Phylogenetic Tree Construction Using Stochastic Optimization And Clustering, Ling Qin, Yixin Chen, Yi Pan, Ling Chen

Computer Science Faculty Publications

Background: The problem of inferring the evolutionary history and constructing the phylogenetic tree with high performance has become one of the major problems in computational biology.

Results: A new phylogenetic tree construction method from a given set of objects (proteins, species, etc.) is presented. As an extension of ant colony optimization, this method proposes an adaptive phylogenetic clustering algorithm based on a digraph to find a tree structure that defines the ancestral relationships among the given objects.

Conclusion: Our phylogenetic tree construction method is tested to compare its results with that of the genetic algorithm (GA). Experimental results show that …

Zsbt: A Novel Algorithm For Tracing Dos Attackers In Manets, Xin Jin, Yaoxue Zhang, Yi Pan, Yuezhi Zhou

Computer Science Faculty Publications

Denial of service (DoS) attack is a major class of security threats today. They consume resources of remote hosts or network and make them deny or degrade services for legitimate users. Compared with traditional Internet, the resources, such as bandwidth, memory, and battery power, of each node are more limited in mobile ad hoc networks (MANETs). Therefore, nodes in MANETs are more vulnerable to DoS attacks. Moreover, attackers in MANETs cannot only use IP spoofing to conceal their real identities but also move arbitrarily, which makes it a challenging task to trace a remote attacker in MANETs. In this paper, …

Simulated Annealing Routing And Wavelength Lower Bound Estimation On Wdm Optical Multistage Networks, Ajay K. Katangur, Yi Pan, Martin D. Fraser

Computer Science Faculty Publications

Multistage interconnection networks (MINs) are popular in switching and communication applications and have been used in telecommunication and parallel computing systems for many years. Crosstalk a major problem introduced by an optical MIN, is caused by coupling two signals within a switching element. We focus on an efficient solution to avoiding crosstalk by routing traffic through an N3N optical network to avoid coupling two signals within each switching element using wavelength-division multiplexing (WDM) and a time-division approach. Under the constraint of avoiding crosstalk, the interest is on realizing a permutation that uses the minimum number of passes for routing. This …

Multicasting In Multihop Optical Wdm Networks With Limited Wavelength Conversion, Hong Shen, Yi Pan, John Sum, Susumu Horiguchi

Computer Science Faculty Publications

This paper provides an overview on efficient algorithms for multicasting in optical networks supported by Wavelength Division Multiplexing (WDM) with limited wavelength conversion. We classify the multicast problems according to off-line and on-line in both reliable and unreliable networks. In each problem class, we present efficient algorithms for multicast and multiple multicast and show their performance. We also present efficient schemes for dynamic multicast group membership updating. We conclude the paper by showing possible extension of the presented algorithms for QoS provision.