Sublinear time width-bounded separators and their application to the protein side-chain packing problem

Given d>2 and a set of n grid points Q in ℜ ^d , we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in sublinear time such that Q has at most points on either side of the hyper-plane, and at most points within distance to the hyper-plane, where c _d is a constant for fixed d. In particular, c ₃=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005). This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35. The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA.     

Hypothesis group testing for disjoint pairs

Classical group testing (CGT) is a widely applicable biotechnical technique used to identify a small number of distinguished objects from a population when the presence of any one of these distinguished objects among a group of others produces an observable result. This paper discusses a variant of CGT called group testing for disjoint pairs (GTAP). The difference between the two is that in GTDP, the distinguished items are pairs from, not individual objects in, the population. There are several biological examples of when this abstract model applies. One biological example is DNA hybridization. The presence of pairs of hybridized DNA strands can be detected in a pool of DNA strands. Another situation is the detection of binding interactions between prey and bait proteins. This paper gives a random pooling method, similar in spirit to hypothesis testing, which identifies pairs of objects from a population that collectively have an observable function. This method is simply to apply, achieves good results, is amenable to automation and can be easily modified to compensate for testing errors. M.A. Bishop is supported by AFOSR FA8750-06-C-0007. A.J. Macula is supported by NSF-0436298, AFOSR FA8750-06-C-0007.     

Almost optimal solutions for bin coloring problems

In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio. The research of this paper was partially supported by an NSF CAREER award CCF-0546509.     

基于遗传算法的资源约束型项目调度优化

资源约束型项目调度的优化是一个NP-hard问题,其求解难度随着资源约束项的增多呈指数方式增长,传统的基于Excel表的手工优化方法不能及时计算出有效的资源配置方式,从而影响项目管理人员的资源调度.针对多资源约束型项目调度的优化问题提出基于遗传算法的资源约束型项目调度的优化方法,该算法采用基于活动优先权的十进制编码方式,结合活动的存储邻接矩阵,有效地解决活动调度违例现象;运用优先抢占模式的资源分配方式安排活动资源,避免资源分配中的冲突问题;并为该算法设计了启发式遗传算法的C语言程序,通过计算机的多次迭代运算得出满足资源约束的最优工期.实践结果表明,遗传算法可以快速有效地解决企业项目调度的优化问题,适合在企业项目进度管理中推广运用.     

Three-step estimation in linear mixed models with skew-t distributions

Linear mixed models based on the normality assumption are widely used in health related studies. Although the normality assumption leads to simple, mathematically tractable, and powerful tests, violation of the assumption may easily invalidate the statistical inference. Transformation of variables is sometimes used to make normality approximately true. In this paper we consider another approach by replacing the normal distributions in linear mixed models by skew-t distributions, which account for skewness and heavy tails for both the random effects and the errors. The full likelihood-based estimator is often difficult to use, but a 3-step estimation procedure is proposed, followed by an application to the analysis of deglutition apnea duration in normal swallows. The example shows that skew-t models often entail more reliable inference than Gaussian models for the skewed data.     

Small sample distribution of the likelihood ratio test in the random effects model

In this paper we examine the small sample distribution of the likelihood ratio test in the random effects model which is often recommended for meta-analyses. We find that this distribution depends strongly on the true value of the heterogeneity parameter (between-study variance) of the model, and that the correct p-value may be quite different from its large sample approximation. We recommend that the dependence of the heterogeneity parameter be examined for the data at hand and suggest a (simulation) method for this. Our setup allows for explanatory variables on the study level (meta-regression) and we discuss other possible applications, too. Two data sets are analyzed and two simulation studies are performed for illustration.     

双重分层抽样中的校正估计

校正估计法已被大量运用于抽样调查中,它利用辅助信息构造的校正权重提高了对总体总值（或均值）的估计精度。本文提出了分层抽样中的校正组合比率估计量,并推广到分层双重抽样中。同时给出新估计量的近似方差表达式。最后利用计算机随机模拟验证较正估计量对估计精度的改进。     

On the computation of the noncentral <Emphasis Type="Italic">F</Emphasis> and noncentral beta distribution

Unfortunately many of the numerous algorithms for computing the comulative distribution function (cdf) and noncentrality parameter of the noncentral F and beta distributions can produce completely incorrect results as demonstrated in the paper by examples. Existing algorithms are scrutinized and those parts that involve numerical difficulties are identified. As a result, a pseudo code is presented in which all the known numerical problems are resolved. This pseudo code can be easily implemented in programming language C or FORTRAN without understanding the complicated mathematical background. Symbolic evaluation of a finite and closed formula is proposed to compute exact cdf values. This approach makes it possible to check quickly and reliably the values returned by professional statistical packages over an extraordinarily wide parameter range without any programming knowledge. This research was motivated by the fact that a very useful table for calculating the size of detectable effects for ANOVA tables contains suspect values in the region of large noncentrality parameter values compared to the values obtained by Patnaik’s 2-moment central-F approximation. The cause is identified and the corrected form of the table for ANOVA purposes is given. The accuracy of the approximations to the noncentral-F distribution is also discussed. The authors wish to thank Mr. Richárd Király for his preliminary work. The authors are grateful to the Editor and Associate Editor of STCO and the unknown reviewers for their helpful suggestions.     

A mixture model for random graphs

The Erdös–Rényi model of a network is simple and possesses many explicit expressions for average and asymptotic properties, but it does not fit well to real-world networks. The vertices of those networks are often structured in unknown classes (functionally related proteins or social communities) with different connectivity properties. The stochastic block structures model was proposed for this purpose in the context of social sciences, using a Bayesian approach. We consider the same model in a frequentest statistical framework. We give the degree distribution and the clustering coefficient associated with this model, a variational method to estimate its parameters and a model selection criterion to select the number of classes. This estimation procedure allows us to deal with large networks containing thousands of vertices. The method is used to uncover the modular structure of a network of enzymatic reactions.