Recent advances in DNA sequencing have made it possible to sequence the whole transcriptome by massively parallel sequencing, commonly referred as RNA-Seq. RNA-Seq is quickly becoming the technology of choice for transcriptome research and analyses. RNA-Seq allows to reduce the sequencing cost and significantly increase data throughput, but it is computationally challenging to use such RNA-Seq data for reconstructing of full length transcripts and accurately estimate their abundances across all cell types. A number of recent works have addressed the problem of transcriptome reconstruction from RNA-Seq reads. These methods fall into three categories: genome-guided, genome-independent and annotation-guided. In this work, we propose a novel statistical genome-guided method called “ T ranscriptome R econstruction using I nteger P rograming” (TRIP) that incorporates fragment length distribution into novel transcript reconstruction from paired-end RNA-Seq reads. To reconstruct novel transcripts, we create a splice graph based on inferred exon boundaries and RNA-Seq reads. A splice graph is a directed acyclic graph (DAG), whose vertices represent exons and edges represent splicing events. We enumerate all maximal paths in the splice graph using a depth-first-search (DFS) algorithm. These paths correspond to putative transcripts and are the input for the TRIP algorithm. To solve the transcriptome reconstruction problem we must select a set of putative transcripts with the highest support from the RNA-Seq reads. We formulate this problem as an integer program. The objective to select the smallest set of putative transcripts that yields a good statistical fit between the fragment length distribution empirically determined during library preparation and fragment lengths implied by mapping read pairs to selected transcripts. 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.

MOTIVATION: In complex disorders, independently evolving locus pairs might interact to confer disease susceptibility, with only a modest effect at each locus. With genome-wide association studies on large cohorts, testing all pairs for interaction confers a heavy computational burden, and a loss of power due to large Bonferroni-like corrections. Correspondingly, limiting the tests to pairs that show marginal effect at either locus, also has reduced power. Here, we describe an algorithm that discovers interacting locus pairs without explicitly testing all pairs, or requiring a marginal effect at each locus. The central idea is a mathematical transformation that maps 'statistical correlation between locus pairs' to 'distance between two points in a Euclidean space'. This enables the use of geometric properties to identify proximal points (correlated locus pairs), without testing each pair explicitly. For large datasets (∼ 10(6) SNPs), this reduces the number of tests from 10(12) to 10(6), significantly reducing the computational burden, without loss of power. The speed of the test allows for correction using permutation-based tests. The algorithm is encoded in a tool called RAPID (RApid Pair IDentification) for identifying paired interactions in case-control GWAS. RESULTS: We validated RAPID with extensive tests on simulated and real datasets. On simulated models of interaction, RAPID easily identified pairs with small marginal effects. On the benchmark disease, datasets from The Wellcome Trust Case Control Consortium, RAPID ran in about 1 CPU-hour per dataset, and identified many significant interactions. In many cases, the interacting loci were known to be important for the disease, but were not individually associated in the genome-wide scan. AVAILABILITY: http://bix.ucsd.edu/projects/rapid.

Emerging microarray technologies allow affordable typing of very long genome sequences. A key challenge in analyzing of such huge amount of data is scalable and accurate computational inferring of haplotypes (i.e., splitting of each genotype into a pair of corresponding haplotypes). In this paper, we first phase genotypes consisting only of two SNPs using genotypes frequencies adjusted to the random mating model and then extend phasing of two-SNP genotypes to phasing of complete genotypes using maximum spanning trees. Runtime of the proposed 2SNP algorithm is O(nm (n + log m), where n and m are the numbers of genotypes and SNPs, respectively, and it can handle genotypes spanning entire chromosomes in a matter of hours. On datasets across 23 chromosomal regions from HapMap[11], 2SNP is several orders of magnitude faster than GERBIL and PHASE while matching them in quality measured by the number of correctly phased genotypes, single-site and switching errors. For example the 2SNP software phases entire chromosome (10(5) SNPs from HapMap) for 30 individuals in 2 hours with average switching error 7.7%. We have also enhanced 2SNP algorithm to phase family trio data and compared it with four other well-known phasing methods on simulated data from [15]. 2SNP is much faster than all of them while loosing in quality only to PHASE. 2SNP software is publicly available at http://alla.cs.gsu.edu/~software/2SNP.

Recent improvements in high-throughput genotyping technology make possible genome-wide association studies and status prediction (classification) for common complex diseases. This paper addresses three challenges commonly facing such studies: (i) searching an enormous amount of possible gene interactions, (ii) validating reproducibility of associations and (iii) reliably predicting disease status. These challenges have been traditionally addressed in statistics while here we apply computational approaches -optimization and cross-validation. A complex risk factor is modeled as a subset of SNP's with specified alleles and the optimization formulation asks for the one with the maximum odds ratio. When searching for disease associated risk factor, we show that greedy heuristics are much faster and lead to significantly better solutions than exhaustive heuristics in a reasonable amount of time. We propose a novel randomized complimentary greedy search method that is advantageous to the previously best search method. To measure and compare ability of search methods to find reproducible risk factors, we propose to apply a cross-validation scheme usually used for prediction validation. The proposed heuristic association search methods promise better reproducibility than exhaustive searches. We then show that k-fold cross-validation is more reliable than leave-one-out cross-validation for disease status prediction methods since it captures overtraining effect. We have applied known search methods with proposed enhancements as well as status prediction methods (based on these search methods) to real case-control studies for several diseases (Chron's disease, autoimmune disorder, tick-born encephalitis, lung cancer, and rheumatoid arthritis). 2-and 3-fold cross-validations show that the new methods find strongly associated risk factors and reliably predict disease status for considered case-control studies.

This paper addresses the computational challenge facing association analysis of case-control studies - searching an enormous amount of possible gene interactions. A complex risk factor (RF) is proposed to be modeled as close (weighted) match to a diplotype (e.g., no more than k mismatches) and the optimization formulation asks for RF with the maximum odds ratio. We have applied and cross-validated previously known and two proposed search methods for finding basic RF's with large odds ratios on 5 real case-control studies. New proposed methods find RF's that are statistically significant on all data including two datasets where no significant RF's were found before. The found RF's explain 1.5-4 times more cases than previously known RF's. The new methods also have significantly higher leave-half-out cross-validation rate.

Energy consumption in monitoring and communication protocols for wireless sensor networks became one of the most important performance objective. We assume a commonly accepted sensor network model in which sensors can interchange idle and active modes both for monitoring and communicating. We introduce a reliability requirement for distributed target-monitoring protocols and prove that previously considered protocols (P. Berman et al., 2004) are reliable. In this paper we propose a new deterministic energy-efficient protocol for sensor networks (DEEPS) aimed at prolonging the lifetime. We prove that DEEPS is reliable and compare DEEPS with several known target-monitoring protocols in NS2 environment using LEACH (W. Heizelman et al., 2002) protocol for data delivery to the base. We implemented the full-fledged simulation of the monitoring protocols on NS2 combined with LEACH as a communication protocol, and performed extensive experimental study of several protocols showing almost 2 times increase in the lifetime for DEEPS over known protocols

2SNP software package implements a new very fast scalable algorithm for haplotype inference based on genotype statistics collected only for pairs of SNPs. This software can be used for comparatively accurate phasing of large number of long genome sequences, e.g. obtained from DNA arrays. As an input 2SNP takes genotype matrix and outputs the corresponding haplotype matrix. On datasets across 79 regions from HapMap 2SNP is several orders of magnitude faster than GERBIL and PHASE while matching them in quality measured by the number of correctly phased genotypes, single-site and switching errors. For example, 2SNP requires 41 s on Pentium 4 2 Ghz processor to phase 30 genotypes with 1381 SNPs (ENm010.7p15:2 data from HapMap) versus GERBIL and PHASE requiring more than a week and admitting no less errors than 2SNP.

Optimizing the energy consumption in monitoring and communication protocols for wireless sensor networks has become the most important performance objective. We explore the problem of maximizing sensor network lifetime, i.e., time during which the set of targets is covered. We propose centralized algorithms for lifetime maximization with provable approximation ratio for the realistic model studied. In this paper we introduce reliability requirement for distributed target-monitoring protocols and prove that previously considered protocols are reliable. A new deterministic energy-efficient protocol for sensor networks (DEEPS) aimed at prolonging lifetime is proposed. We prove that DEEPS is reliable and compare DEEPS with several known target-monitoring protocols in NS2 environment using LEACH (W. Heinzelman et al., 2000) for simulating monitoring data delivery to the base. Our contributions also include the first full-fledged simulation of the monitoring protocols on NS2 combined with LEACH (W. Heinzelman et al., 2000) as a communication protocol, and extensive experimental study of several protocols showing almost 2 times increase in the lifetime for DEEPS over known protocols