29942985
Poisson approximation for significance in genome-wide ChIP-chip tiling arrays
MOTIVATION
A genome-wide ChIP-chip tiling array study requires millions of simultaneous comparisons of hybridization for significance. Controlling the false positive rate in genome-wide tiling array studies is very important, because the number of computationally identified regions can easily go beyond the capability of experimental verification. No accurate and efficient method exists for evaluating statistical significance in tiling arrays. The Bonferroni method is overly conservative and the permutation test is time consuming for genome-wide studies.


RESULT
Motivated by the Poisson clumping heuristic, we propose an accurate and efficient method for evaluating statistical significance in genome-wide ChIP-chip tiling arrays. The method works accurately for any large number of multiple comparisons, and the computational cost for evaluating P-values does not increase with the total number of tests. Based on a moving window approach, we demonstrate how to combine results using various window sizes to increase the detection power while maintaining a specified type I error rate. We further introduce a new false discovery rate control that is more appropriate in measuring the false proportion of binding intervals in tiling array analysis. Our method is general and can be applied to many large-scale genomic and genetic studies.


AVAILABILITY
http://www.stat.psu.edu/~yuzhang/pass.tar
12935102
Whole-Genome Analysis of Gene Conversion Events
Gene conversion events are often overlooked in analyses of genome evolution. In a conversion event, an interval of DNA sequence (not necessarily containing a gene) overwrites a highly similar sequence. The event creates relationships among genomic intervals that can confound attempts to identify orthologs and to transfer functional annotation between genomes. Here we examine 1,112,202 paralogous pairs of human genomic intervals, and detect conversion events in about 13.5% of them. Properties of the putative gene conversions are analyzed, such as the lengths of the paralogous pairs and the spacing between their sources and targets. Our approach is illustrated using conversion events in the beta-globin gene cluster.
12263549
Tree-guided Bayesian inference of population structures
MOTIVATION
Inferring population structures using genetic data sampled from a group of individuals is a challenging task. Many methods either consider a fixed population number or ignore the correlation between populations. As a result, they can lose sensitivity and specificity in detecting subtle stratifications. In addition, when a large number of genetic markers are used, many existing algorithms perform rather inefficiently.


RESULT
We propose a new Bayesian method to infer population structures using multiple unlinked single nucleotide polymorphisms (SNPs). Our approach explicitly considers the population correlation through a tree hierarchy, and treat the population number as a random variable. Using both simulated and real datasets of worldwide samples, we demonstrate that an incorporated tree can consistently improve the power in detecting subtle population stratifications. A tree-based model often involves a large number of unknown parameters, and the corresponding estimation procedure can be highly inefficient. We further implement a partition method to analytically integrate out all nuisance parameters in the tree. As a result, our method can analyze large SNP datasets with significantly improved convergence rate.


AVAILABILITY
http://www.stat.psu.edu/~yuzhang/tips.tar.
32462907
Alignment of Optical Maps
We introduce a new scoring method for calculation of alignments of optical maps. Missing cuts, false cuts, and sizing errors present in optical maps are addressed by our alignment score through calculation of corresponding likelihoods. The size error model is derived through the application of Central Limit Theorem and validated by residual plots collected from real data. Missing cuts and false cuts are modeled as Bernoulli and Poisson events, respectively, as suggested by previous studies. Likelihoods are used to derive an alignment score through calculation of likelihood ratios for a certain hypothesis test. This allows us to achieve maximal descriminative power for the alignment score. Our scoring method is naturally embedded within a well known DP framework for finding optimal alignments.
15564677
Handover Latency of MIPv6 Implementation in Linux
Mobile IPv6 (MIPv6) is proposed to enable network applications to continuously operate at the required quality of service in the wire or wireless IP network. Handover latency of MIPv6 is the main cause of packet loss and performance degradation and is too long for real-time and throughput-sensitive applications. Enhancement of basic MIPv6 with respect to handover latency has been studied widely. A L3 handover procedure can be divided into four phases: Movement Detection, CoA Configuration, Home agent Registration and Route Optimization. The latencies in different handover phases have been measured in an operated wireless LAN (WLAN) in order to determine the performance bottleneck of handover. The effect of handover latency on the sliding window of TCP and application layer protocol is also parsed with experiment. Further more, we modify the MIPv6 implementations of Linux on mobile node and home agent to verify the potential of performance improvement for MIPv6 protocol. The experiment result can help the enhancement of MIPv6 and application development.
14272122
A Dynamic Immunity-Based Model for Computer Virus Detection
Internet provides a fertile medium for new breeds of computer viruses. Many people who have access to a wealth of information via Internet are attacked by more computer viruses than they can effectively process. We present a dynamic computer virus detection model that can detect known viruses and previously unknown viruses to prevent information systems from damage. This model is inspired by biological immune systems that protect the body against damage from pathogens. The architecture of this model, the formal definitions of self, nonself, antigen, antibody, and vaccine gene library are introduced. Furthermore, the evolution of self and nonself, the generation of the antibody, the evolution of the virus vaccine gene, and the detection of the antigen are depicted. Experiment results show that this model has better capacity of self-adaptability and self-learning in detecting unknown viruses than traditional models.
29802848
Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows
Detecting duplicates in data streams is an important problem that has a wide range of applications. In general, precisely detecting duplicates in an unbounded data stream is not feasible in most streaming scenarios, and, on the other hand, the elements in data streams are always time sensitive. These make it particular significant approximately detecting duplicates among newly arrived elements of a data stream within a fixed time frame. In this paper, we present a novel data structure, Decaying Bloom Filter (DBF), as an extension of the Counting Bloom Filter, that effectively removes stale elements as new elements continuously arrive over sliding windows. On the DBF basis we present an efficient algorithm to approximately detect duplicates over sliding windows. Our algorithm may produce false positive errors, but not false negative errors as in many previous results. We analyze the time complexity and detection accuracy, and give a tight upper bound of false positive rate. For a given space G bits and sliding window size W, our algorithm has an amortized time complexity of $ O + (\sqrt{G/W}) $. Both analytical and experimental results on synthetic data demonstrate that our algorithm is superior in both execution time and detection accuracy to the previous results.
34552917
A new dynamic Bayesian network for integrating multiple data in estimating gene networks
We propose a novel method for estimating a gene regulatory network from both gene expression data and transcription factor binding location data. Based on dynamic Bayesian network (DBN) models, our method has two advantages. First, structural expectation maximization algorithm is embedded into a DBN framework, allowing it to learn the network with unknown structure and incomplete data, which cannot be tackled by expectation maximization algorithm. Second, since learning only from gene expression data is not enough to accurately estimate a gene network, we incorporate transcription factor binding location data through a structure prior. We demonstrate the effectiveness of the proposed method by the analysis of Saccharomyces Cerevisiae cell cycle data. The experimental results show that this new approach suits for dealing with missing values. Furthermore, combination of heterogeneous data from multiple sources ensures that our results are more accurate than those recovered from gene expression data alone.
21919804
Logical Relations for Dynamic Name Creation
Pitts and Stark’s nu-calculus is a typed lambda-calculus which forms a basis for the study of interaction between higher-order functions and dynamically created names. A similar approach has received renewed attention recently through Sumii and Pierce’s cryptographic lambda-calculus, which deals with security protocols. Logical relations are a powerful tool to prove properties of such a calculus, notably observational equivalence. While Pitts and Stark construct a logical relation for the nu-calculus, it rests heavily on operational aspects of the calculus and is hard to be extended. We propose an alternative Kripke logical relation for the nu-calculus, which is derived naturally from the categorical model of the nu-calculus and the general notion of Kripke logical relation. This is also related to the Kripke logical relation for the name creation monad by Goubault-Larrecq et al. (CSL’2002), which the authors claimed had similarities with Pitts and Stark’s logical relation. We show that their Kripke logical relation for names is strictly weaker than Pitts and Stark’s. We also show that our Kripke logical relation, which extends the definition of Goubault-Larrecq et al., is equivalent to Pitts and Stark’s up to first-order types; our definition rests on purely semantic constituents, and dispenses with the detours through operational semantics that Pitts and Stark use.