A linear programming approach for estimating the structure of a sparse linear genetic network from transcript profiling data

Background: A genetic network can be represented as a directed graph in which a node corresponds to a gene and a directed edge specifies the direction of influence of one gene on another. The reconstruction of such networks from transcript profiling data remains an important yet challenging endeavor. A transcript profile specifies the abundances of many genes in a biological sample of interest. Prevailing strategies for learning the structure of a genetic network from high-dimensional transcript profiling data assume sparsity and linearity. Many methods consider relatively small directed graphs, inferring graphs with up to a few hundred nodes. This work examines large undirected graphs representations of genetic networks, graphs with many thousands of nodes where an undirected edge between two nodes does not indicate the direction of influence, and the problem of estimating the structure of such a sparse linear genetic network (SLGN) from transcript profiling data. Results: The structure learning task is cast as a sparse linear regression problem which is then posed as a LASSO (l1-constrained fitting) problem and solved finally by formulating a Linear Program (LP). A bound on the Generalization Error of this approach is given in terms of the Leave-One-Out Error. The accuracy and utility of LP-SLGNs is assessed quantitatively and qualitatively using simulated and real data. The Dialogue for Reverse Engineering Assessments and Methods (DREAM) initiative provides gold standard data sets and evaluation metrics that enable and facilitate the comparison of algorithms for deducing the structure of networks. The structures of LP-SLGNs estimated from the INSILICO1, INSILICO2 and INSILICO3 simulated DREAM2 data sets are comparable to those proposed by the first and/or second ranked teams in the DREAM2 competition. The structures of LP-SLGNs estimated from two published Saccharomyces cerevisae cell cycle transcript profiling data sets capture known regulatory associations. In each S. cerevisiae LP-SLGN, the number of nodes with a particular degree follows an approximate power law suggesting that its degree distributions is similar to that observed in real-world networks. Inspection of these LP-SLGNs suggests biological hypotheses amenable to experimental verification. Conclusion: A statistically robust and computationally efficient LP-based method for estimating the topology of a large sparse undirected graph from high-dimensional data yields representations of genetic networks that are biologically plausible and useful abstractions of the structures of real genetic networks. Analysis of the statistical and topological properties of learned LP-SLGNs may have practical value; for example, genes with high random walk betweenness, a measure of the centrality of a node in a graph, are good candidates for intervention studies and hence integrated computational – experimental investigations designed to infer more realistic and sophisticated probabilistic directed graphical model representations of genetic networks. The LP-based solutions of the sparse linear regression problem described here may provide a method for learning the structure of transcription factor networks from transcript profiling and transcription factor binding motif data.

Expression Profiling of Nucleotide Metabolism-Related Genes in Human Breast Cancer Cells After Treatment with 5-Fluorouracil

5-Fluorouracil (5-FU) is one of the most widely used drugs for treatment of cancers, including breast cancer that exhibits its anticancer activity by inhibiting DNA synthesis and also incorporated into DNA and RNA. The objective of this investigation was to find out the total nucleotide metabolism genes regulated by 5-FU in breast cancer cell line. The breast cancer cell line MCF-7 was treated with the drug 5-FU. To analyze the expression of genes, we have conducted the experiment using 1.7k and 19k human microarray slide and confirmed the expression of genes by semiquantitative reverse transcription-polymerase chain reaction. The expression of 44 genes involved in the nucleotide metabolism pathway was quantified. Of these 44 genes analyzed, transcription of 6 genes were upregulated and 9 genes were downregulated. Earlier studies revealed that the transcription of genes for key enzymes like thymidylate synthase, thymidinekinase, and dihydropyrimidine dehydrogenase are regulated by 5-FU. This study identified some novel genes like thioredoxin reductase, ectonucleotide triphosphate dephosphorylase, and CTP synthase are regulated by 5-FU. The data also reveal large-scale perturbation in transcription of genes not involved directly in the known mechanism of action of 5-FU.

Three-User Cognitive Channels with Cumulative Message Sharing: An Achievable Rate Region

In this paper, an achievable rate region for the three-user discrete memoryless interference channel with asymmetric transmitter cooperation is derived. The three-user channel facilitates different ways of message sharing between the transmitters. We introduce a manner of noncausal (genie aided) unidirectional message-sharing, which we term cumulative message sharing. We consider receivers with predetermined decoding capabilities, and define a cognitive interference channel. We then derive an achievable rate region for this channel by employing a coding scheme which is a combination of superposition and Gel'fand-Pinsker coding techniques.

Gene expression profiling during Forskolin induced differentiation of BeWo cells by differential display RT-PCR

The differentiation of cytotrophoblasts into syncytiotrophoblasts in the placenta has been employed as a model to investigate stage specific expression as well as regulation of genes during this process. While the cytotrophoblasts are highly invasive and proliferative with relatively less capacity to synthesize pregnancy related proteins, the multinucleated syncytiotrophoblasts are non-proliferative and non-invasive. However, syncytiotrophoblasts are the site of synthesis of a variety of protein, peptide and steroid hormones as well as several growth factors. Both the freshly isolated cytotrophoblasts from human placenta as well as the BeWo cell, a choriocarcinoma cell line model which retain several characteristic of cytotrophoblasts has been employed by us to study regulation of differentiation. In the present study, we have employed the differential display RT-PCR analysis (DD-RT-PCR) to evaluate gene expression changes during Forskolin induced in vitro differentiation of BeWo cells. We have identified several genes which are differentially expressed during differentiation and the differential expression of 10 transcripts was confirmed by Northern blot analysis. Based on the identity of the transcripts an attempt has been made to relate the known function of the gene products, to changes observed during differentiation. Of the several transcripts, one of the transcripts, namely Secretory Leukocyte Protease Inhibitor (SLPI) which is known to have multiple functions was found to increase 15-fold in the syntiotrophoblast.

Proteomic profiling of forskolin-induced differentiated BeWo cells: an in-vitro model of cytotrophoblast differentiation

Placental trophoblastic differentiation is characterized by the fusion of monolayer cytotrophoblasts into syncytiotrophoblasts. During this process of differentiation, several morphological and biochemical changes are known to occur, and this model has been employed to investigate the changes that occur at the gene and protein level during differentiation. Using the sensitive technique of proteomics [two-dimensional gel electrophoresis (2DGE)], changes in protein profile were evaluated in the control and forskolin-induced differentiated cells of trophoblastic choriocarcinoma BeWo cell line. Several proteins were differentially expressed in control and differentiated cells. Four major proteins were up-regulated as assessed by silver staining, and were further characterized as c-h-ras p 21 (phosphorylated), retinoblastoma susceptibility protein I and integrase interactor protein 1. These proteins are known to play an important role in growth arrest of cells, and thus may play a role in initiating the process of differentiation.

Selective dissemination of XML documents based on genetically learned user model and Support Vector Machines

Extensible Markup Language ( XML) has emerged as a medium for interoperability over the Internet. As the number of documents published in the form of XML is increasing, there is a need for selective dissemination of XML documents based on user interests. In the proposed technique, a combination of Adaptive Genetic Algorithms and multi class Support Vector Machine ( SVM) is used to learn a user model. Based on the feedback from the users, the system automatically adapts to the user's preference and interests. The user model and a similarity metric are used for selective dissemination of a continuous stream of XML documents. Experimental evaluations performed over a wide range of XML documents, indicate that the proposed approach significantly improves the performance of the selective dissemination task, with respect to accuracy and efficiency.

Profiling k-Iteration Paths : A Generalization of the Ball-Larus Profiling Algorithm

The Ball-Larus path-profiling algorithm is an efficient technique to collect acyclic path frequencies of a program. However, longer paths -those extending across loop iterations - describe the runtime behaviour of programs better. We generalize the Ball-Larus profiling algorithm for profiling k-iteration paths - paths that can span up to to k iterations of a loop. We show that it is possible to number suchk-iteration paths perfectly, thus allowing for an efficient profiling algorithm for such longer paths. We also describe a scheme for mixed-mode profiling: profiling different parts of a procedure with different path lengths. Experimental results show that k-iteration profiling is realistic.

Selective dissemination of XML documents based on genetically learned user model and Support Vector Machines

Extensible Markup Language ( XML) has emerged as a medium for interoperability over the Internet. As the number of documents published in the form of XML is increasing, there is a need for selective dissemination of XML documents based on user interests. In the proposed technique, a combination of Adaptive Genetic Algorithms and multi class Support Vector Machine ( SVM) is used to learn a user model. Based on the feedback from the users, the system automatically adapts to the user's preference and interests. The user model and a similarity metric are used for selective dissemination of a continuous stream of XML documents. Experimental evaluations performed over a wide range of XML documents, indicate that the proposed approach significantly improves the performance of the selective dissemination task, with respect to accuracy and efficiency.

Discovering user preferences by using time entries in click-through data to improve search engine results

The search engine log files have been used to gather direct user feedback on the relevancy of the documents presented in the results page. Typically the relative position of the clicks gathered from the log files is used a proxy for the direct user feedback. In this paper we identify reasons for the incompleteness of the relative position of clicks for deciphering the user preferences. Hence, we propose the use of time spent by the user in reading through the document as indicative of user preference for a document with respect to a query. Also, we identify the issues involved in using the time measure and propose means to address them.

Coding for Two-User Gaussian MAC with PSK and PAM Signal Sets

Constellation Constrained (CC) capacity regions of a two-user Gaussian Multiple Access Channel(GMAC) have been recently reported. For such a channel, code pairs based on trellis coded modulation are proposed in this paper with MPSK and M-PAM alphabet pairs, for arbitrary values of M,toachieve sum rates close to the CC sum capacity of the GMAC. In particular, the structure of the sum alphabets of M-PSK and M-PAMmalphabet pairs are exploited to prove that, for certain angles of rotation between the alphabets, Ungerboeck labelling on the trellis of each user maximizes the guaranteed squared Euclidean distance of the sum trellis. Hence, such a labelling scheme can be used systematically,to construct trellis code pairs to achieve sum rates close to the CC sum capacity. More importantly, it is shown for the first time that ML decoding complexity at the destination is significantly reduced when M-PAM alphabet pairs are employed with almost no loss in the sum capacity.

Constellation Constrained Capacity of Two-user Broadcast Channels

Capacity region for two-user Gaussian Broadcast Channels (GBC) is well known with the optimal input being Gaussian. In this paper we explore the capacity region for GBC when the users' symbols are taken from finite complex alphabets (like M-QAM, M-PSK). When the alphabets for both the users are the same we show that rotation of one of the alphabets enlarges the capacity region. We arrive at an optimal angle of rotation by simulation. The effect of rotation on the capacity region at different SNRs is also studied using simulation results. Using the setup of Fading Broadcast Channel (FBC) given by [Li and Goldsmith, 2001], we study the ergodic capacity region with inputs from finite complex alphabets. It is seen that, using the procedure for optimum power allocation obtained in [Li and Goldsmith, 2001] for Gaussian inputs, to allocate power to symbols from finite complex alphabets, relative rotation between the alphabets does not improve the capacity region. Simulation results for a modified heuristic power allocation procedure for finite-constellation case, show that Constellation Constrained capacity region enlarges with rotation.

Information Theoretic Results for Three-User Cognitive Channels

In this paper, we introduce the three-user cognitive radio channels with asymmetric transmitter cooperation, and derive achievable rate regions under several scenarios depending on the type of cooperation and decoding capability at the receivers. Two of the most natural cooperation mechanisms for the three-user channel are considered here: cumulative message sharing (CMS) and primary-only message sharing (PMS). In addition to the message sharing mechanism, the achievable rate region is critically dependent on the decoding capability at the receivers. Here, we consider two scenarios for the decoding capability, and derive an achievable rate region for each one of them by employing a combination of superposition and Gel'fand-Pinsker coding techniques. Finally, to provide a numerical example, we consider the Gaussian channel model to plot the rate regions. In terms of achievable rates, CMS turns out to be a better scheme than PMS. However, the practical aspects of implementing such message-sharing schemes remain to be investigated.

STBCs with Reduced Sphere Decoding Complexity for Two-User MIMO-MAC

In this paper, Space-Time Block Codes (STBCs) with reduced Sphere Decoding Complexity (SDC) are constructed for two-user Multiple-Input Multiple-Output (MIMO) fading multiple access channels. In this set-up, both the users employ identical STBCs and the destination performs sphere decoding for the symbols of the two users. First, we identify the positions of the zeros in the R matrix arising out of the Q-R decomposition of the lattice generator such that (i) the worst case SDC (WSDC) and (ii) the average SDC (ASDC) are reduced. Then, a set of necessary and sufficient conditions on the lattice generator is provided such that the R matrix has zeros at the identified positions. Subsequently, explicit constructions of STBCs which results in the reduced ASDC are presented. The rate (in complex symbols per channel use) of the proposed designs is at most 2/N-t where N-t denotes the number of transmit antennas for each user. We also show that the class of STBCs from complex orthogonal designs (other than the Alamouti design) reduce the WSDC but not the ASDC.

Genome-wide expression profiling identifies deregulated miRNAs in malignant astrocytoma

Malignant astrocytoma includes anaplastic astrocytoma (grade III) and glioblastoma (grade IV). Among them, glioblastoma is the most common primary brain tumor with dismal responses to all therapeutic modalities. We performed a large-scale, genome-wide microRNA (miRNA) (n=756) expression profiling of 26 glioblastoma, 13 anaplastic astrocytoma and 7 normal brain samples with an aim to find deregulated miRNA in malignant astrocytoma. We identified several differentially regulated miRNAs between these groups, which could differentiate glioma grades and normal brain as recognized by PCA. More importantly, we identified a most discriminatory 23-miRNA expression signature, by using PAM, which precisely distinguished glioblastoma from anaplastic astrocytoma with an accuracy of 95%. The differential expression pattern of nine miRNAs was further validated by real-time RT-PCR on an independent set of malignant astrocytomas (n-72) and normal samples (n=7). Inhibition of two glioblastoma-upregulated miRNAs (miR-21 and miR-23a) and exogenous overexpression of two glioblastoma-downregulated miRNAs (miR-218 and miR-219-5p) resulted in reduced soft agar colony formation but showed varying effects on cell proliferation and chemosensitivity. Thus we have identified the miRNA expression signature for malignant astrocytoma, in particular glioblastoma, and showed the miRNA involvement and their importance in astrocytoma development. Modern Pathology (2010) 23, 1404-1417; doi:10.1038/modpathol.2010.135; published online 13 August 2010

On Two-User Gaussian Multiple Access Channels With Finite Input Constellations

Constellation Constrained (CC) capacity regions of two-user Single-Input Single-Output (SISO) Gaussian Multiple Access Channels (GMAC) are computed for several Non-Orthogonal Multiple Access schemes (NO-MA) and Orthogonal Multiple Access schemes (O-MA). For NO-MA schemes, a metric is proposed to compute the angle(s) of rotation between the input constellations such that the CC capacity regions are maximally enlarged. Further, code pairs based on Trellis Coded Modulation (TCM) are designed with PSK constellation pairs and PAM constellation pairs such that any rate pair within the CC capacity region can be approached. Such a NO-MA scheme which employs CC capacity approaching trellis codes is referred to as Trellis Coded Multiple Access (TCMA). Then, CC capacity regions of O-MA schemes such as Frequency Division Multiple Access (FDMA) and Time Division Multiple Access (TDMA) are also computed and it is shown that, unlike the Gaussian distributed continuous constellations case, the CC capacity regions with FDMA are strictly contained inside the CC capacity regions with TCMA. Hence, for finite constellations, a NO-MA scheme such as TCMA is better than FDMA and TDMA which makes NO-MA schemes worth pursuing in practice for two-user GMAC. Then, the idea of introducing rotations between the input constellations is used to construct Space-Time Block Code (STBC) pairs for two-user Multiple-Input Single-Output (MISO) fading MAC. The proposed STBCs are shown to have reduced Maximum Likelihood (ML) decoding complexity and information-losslessness property. Finally, STBC pairs with reduced sphere decoding complexity are proposed for two-user Multiple-Input Multiple-Output (MIMO) fading MAC.