Forward rate constants for receptor clusters. Variational methods for upper and lower bounds

We are interested in the effect of receptor clustering on k+, the diffusion-limited forward rate constant for the binding of a ligand to a cell surface receptor. Here we estimate the reduction in k+ when receptors are clustered in various configurations. We obtain two alternative expressions for the flux of ligands into receptors distributed on a surface. Next we show through a variational principle that these provide both upper and lower bounds on the flux when evaluated for trial concentration functions which satisfy only the boundary conditions of the Laplace equation. We use an analogy with electrostatics to calculate rigorous bounds within approx. 10% of the exact result for a variety of planar clusters of hemispherical receptor sites. We also obtain an exact result for the flux into a spheroidal receptor and use this result to obtain bounds on the flux into certain receptor clusters.     

The calculation of probabilities in rejecting bioequivalence

Methods are given for deriving the lower and upper bounds of the probabilities for rejecting bioequivalence. Except when two formulations are nearly equal, the lower and upper bounds become very close and thus give an exact probability. The methods can be used in two- or higher-way crossover or parallel groups designs. One can also determine the sample size from the equations. The results are compared with the probabilities obtained by simulation.     

Obtaining maximal concatenated phylogenetic data sets from large sequence databases

To improve the accuracy of tree reconstruction, phylogeneticists are extracting increasingly large multigene data sets from sequence databases. Determining whether a database contains at least k genes sampled from at least m species is an NP-complete problem. However, the skewed distribution of sequences in these databases permits all such data sets to be obtained in reasonable computing times even for large numbers of sequences. We developed an exact algorithm for obtaining the largest multigene data sets from a collection of sequences. The algorithm was then tested on a set of 100,000 protein sequences of green plants and used to identify the largest multigene ortholog data sets having at least 3 genes and 6 species. The distribution of sizes of these data sets forms a hollow curve, and the largest are surprisingly small, ranging from 62 genes by 6 species, to 3 genes by 65 species, with more symmetrical data sets of around 15 taxa by 15 genes. These upper bounds to sequence concatenation have important implications for building the tree of life from large sequence databases.     

Exact methods for the robotic cell problem

This paper investigates an exact method for the Robotic Cell Problem. We present a branch-and-bound algorithm which is the first exact procedure specifically designed with regard to this complex flow shop scheduling variant. Also, we propose a new mathematical programming model as well as new lower bounds. Furthermore, we describe an effective genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that medium-sized instances, with up to 176 operations, can be optimally solved. Also, we found that the new proposed lower bounds outperform lower bounds from the literature. Finally, we show, that the genetic algorithm delivers good solutions while requiring short CPU times.     

Bounds on life expectancy for the Rayleigh and Weibull distributions

Bounds are presented for the life expectancy or the mean residual life of an individual whose lifetime is a random variable X following a Rayleigh distribution or more generally a Weibull distribution. Simple transformations of the variables give inequalities on the Mills' ratio and the incomplete gamma functions. Some numerical computations are also reported to compare the lower and upper bounds with the exact value of the life expectancy function for several values of the parameter. When the lifetime follows a Gompertz distribution, the problem becomes complicated, and it has not been possible to construct bounds on the life expectancy function. The importance of the Gompertz distribution in the dynamics of normal and tumor growth and in the embryonic and postnatal growth of birds and mammals is demonstrated, and life expectancy is evaluated by numerical methods for a number of parameter values.     

The k partition-distance problem

Many applications of data partitioning (clustering) have been well studied in bioinformatics. Consider, for instance, a set N of organisms (elements) based on DNA marker data. A partition divides all elements in N into two or more disjoint clusters that cover all elements, where a cluster contains a non-empty subset of N. Different partitioning algorithms may produce different partitions. To compute the distance and find the consensus partition (also called consensus clustering) between two or more partitions are important and interesting problems that arise frequently in bioinformatics and data mining, in which different distance functions may be considered in different partition algorithms. In this article, we discuss the k partition-distance problem. Given a set of elements N with k partitions of N, the k partition-distance problem is to delete the minimum number of elements from each partition such that all remaining partitions become identical. This problem is NP-complete for general k?>?2 partitions, and no algorithms are known at present. We design the first known heuristic and approximation algorithms with performance ratios 2 to solve the k partition-distance problem in O(k?·?ρ?·?|N|) time, where ρ is the maximum number of clusters of these k partitions and |N| is the number of elements in N. We also present the first known exact algorithm in O(??·?2(?)·k(2)?·?|N|(2)) time, where ? is the partition-distance of the optimal solution for this problem. Performances of our exact and approximation algorithms in testing the random data with actual sets of organisms based on DNA markers are compared and discussed. Experimental results reveal that our algorithms can improve the computational speed of the exact algorithm for the two partition-distance problem in practice if the maximum number of elements per cluster is less than ρ. From both theoretical and computational points of view, our solutions are at most twice the partition-distance of the optimal solution. A website offering the interactive service of solving the k partition-distance problem using our and previous algorithms is available (see http://mail.tmue.edu.tw/~yhchen/KPDP.html).     

Prediction of multilocus identity-by-descent

Previous studies have enabled exact prediction of probabilities of identity-by-descent (IBD) in random-mating populations for a few loci (up to four or so), with extension to more using approximate regression methods. Here we present a precise predictor of multiple-locus IBD using simple formulas based on exact results for two loci. In particular, the probability of non-IBD X(ABC) at each of ordered loci A, B, and C can be well approximated by X(ABC) = X(AB)X(BC)/X(B) and generalizes to X(123...k) = X(12)X(23...)X(k)(-1,k)/X(k-2), where X is the probability of non-IBD at each locus. Predictions from this chain rule are very precise with population bottlenecks and migration, but are rather poorer in the presence of mutation. From these coefficients, the probabilities of multilocus IBD and non-IBD can also be computed for genomic regions as functions of population size, time, and map distances. An approximate but simple recurrence formula is also developed, which generally is less accurate than the chain rule but is more robust with mutation. Used together with the chain rule it leads to explicit equations for non-IBD in a region. The results can be applied to detection of quantitative trait loci (QTL) by computing the probability of IBD at candidate loci in terms of identity-by-state at neighboring markers.     

Error distribution derived NOE distance restraints

Errors and imprecisions in distance restraints derived from NOESY peak volumes are usually accounted for by generous lower and upper bounds on the distances. In this paper, we propose a new form of distance restraints, replacing the subjective bounds by a potential function obtained from the error distribution of the distances. We derived the shape of the potential from molecular dynamics calculations and by comparison of NMR data with X-ray crystal structures. We used complete cross-validation to derive the optimal weight for the data in the calculation. In a model system with synthetic restraints, the accuracy of the structures improved significantly compared to calculations with the usual form of restraints. For experimental data sets, the structures systematically approach the X-ray crystal structures of the same protein. Also standard quality indicators improve compared to standard calculations. The results did not depend critically on the exact shape of the potential. The new approach is less subjective and uses fewer assumptions in the interpretation of NOESY peak volumes as distance restraints than the usual approach. Figures of merit for the structures, such as the RMS difference from the average structure or the RMS difference from the data, are therefore less biased and more meaningful measures of structure quality than with the usual form of restraints.     

Network algorithm for the Exact Test of Hardy‐Weinberg Proportion for Multiple Alleles

We propose a new technique for the exact test of Hardy‐Weinberg proportion that considerably extends the bounds of computational feasibility. Our algorithm is constructed analogously to the network algorithm for Freeman‐Halton exact test in two‐way contingency tables. In this algorithm, the smallest and the largest values for the statistic are important and some interesting new theorems are proved for computing these values. Numerical examples are given to illustrate the practicality of our algorithm.     

Unbiased Confidence Intervals for the Odds Ratio of Two Independent Binomial Samples with Application to Case–Control Data

The problem of confidence interval construction for the odds ratio of two independent binomial samples is considered. Two methods of eliminating the nuisance parameter from the exact likelihood, conditioning and maximization, are described. A conditionally exact tail method exists by putting together upper and lower bounds. A shorter interval can be obtained by simultaneous consideration of both tails. We present here new methods that extend the tail and simultaneous approaches to the maximized likelihood. The methods are unbiased and applicable to case-control data, for which the odds ratio is important. The confidence interval procedures are compared unconditionally for small sample sizes in terms of their expected length and coverage probability. A Bayesian confidence interval method and a large-sample chi2 procedure are included in the comparisons.     

The kinetics of solute clearance by a single tissue capillary of limited permeability: Explicit solutions of two models and their bounds

To describe stationary-state kinetics of solute clearance from an interstitial space with an initial uniform concentration, an explicit solution of the Sangren-Sheppard model and a stratagem for an explicit solution of the Johnson-Wilson model are presented. In both cases expressions for computing the exact intravascular and extravascular concentrations at any time and location are complicated and inconvenient. Simpler and far more convenient formulae for determining upper and lower bounds on solute concentrations and on the pseudo-first-order clearance rate ‘constant’ (k) are derived. For the Johnson-Wilson model, the bounds are so tight thatk, for example, can be estimated with considerable accuracy whenever the capillary blood flow exceeds the permeability-surface area product.     

Simultaneous inference for ratios of linear combinations of general linear model parameters

Consider a general linear model with p -dimensional parameter vector beta and i.i.d. normal errors. Let K(1), ..., K(k ), and L be linearly independent vectors of constants such that L(T)beta not equal 0. We describe exact simultaneous tests for hypotheses that Ki(T)beta/L(T)beta equal specified constants using one-sided and two-sided alternatives, and describe exact simultaneous confidence intervals for these ratios. In the case where the confidence set is a single bounded contiguous set, we describe what we claim are the best possible conservative simultaneous confidence intervals for these ratios - best in that they form the minimum k -dimensional hypercube enclosing the exact simultaneous confidence set. We show that in the case of k = 2, this "box" is defined by the minimum and maximum values for the two ratios in the simultaneous confidence set and that these values are obtained via one of two sources: either from the solutions to each of four systems of equations or at points along the boundary of the simultaneous confidence set where the correlation between two t variables is zero. We then verify that these intervals are narrower than those previously presented in the literature.     

Fixation probabilities for the Moran process with three or more strategies: general and coupling results

We study fixation probabilities for the Moran stochastic process for the evolution of a population with three or more types of individuals and frequency-dependent fitnesses. Contrary to the case of populations with two types of individuals, in which fixation probabilities may be calculated by an exact formula, here we must solve a large system of linear equations. We first show that this system always has a unique solution. Other results are upper and lower bounds for the fixation probabilities obtained by coupling the Moran process with three strategies with birth–death processes with only two strategies. We also apply our bounds to the problem of evolution of cooperation in a population with three types of individuals already studied in a deterministic setting by Núñez Rodríguez and Neves (J Math Biol 73:1665–1690, 2016). We argue that cooperators will be fixated in the population with probability arbitrarily close to 1 for a large region of initial conditions and large enough population sizes.

     

Space efficient computation of rare maximal exact matches between multiple sequences.

In this article, we propose a new method for computing rare maximal exact matches between multiple sequences. A rare match between k sequences S(1), ... , S(k) is a string that occurs at most t(i)-times in the sequence S(i), where the t(i) > 0 are user-defined thresholds. First, the suffix tree of one of the sequences (the reference sequence) is built, and then the other sequences are matched separately against this suffix tree. Second, the resulting pairwise exact matches are combined to multiple exact matches. A clever implementation of this method yields a very fast and space efficient program. This program can be applied in several comparative genomics tasks, such as the identification of synteny blocks between whole genomes.     

A note on the use of the non-central t-distribution in setting numerical microbiological specifications for foods

An exact procedure is described and used to determine k values and probabilities of rejection used in the application of variables sampling plans to foods. Comparison of quantities so obtained to those calculated by Kilsby et al. (1979), who used an approximation procedure, reveals that for small samples the approximation can lead to probabilities of rejection which are larger than those obtained using the exact procedure. It is recommended that the exact procedure be used in the application of these plans.     

Shufflet: shuffling sequences while conserving the k-let counts

Shufflet is a program and a web-application that generates fast random shufflings of sequences (DNA, protein or others), conserving the exact k-let counts for a given k. The sequences are sampled uniformly from all the valid permutations.     

Ranking-based kernels in applied biomedical diagnostics using a support vector machine

This paper presents some essential findings and results on using ranking-based kernels for the analysis and utilization of high dimensional and noisy biomedical data in applied clinical diagnostics. We claim that presented kernels combined with a state-of-the-art classification technique - a Support Vector Machine (SVM) - could significantly improve the classification rate and predictive power of the wrapper method, e.g. SVM. Moreover, the advantage of such kernels could be potentially exploited for other kernel methods and essential computer-aided tasks such as novelty detection and clustering. Our experimental results and theoretical generalization bounds imply that ranking-based kernels outperform other traditionally employed SVM kernels on high dimensional biomedical and microarray data.     

An algorithm for approximate tandem repeats.

A perfect single tandem repeat is defined as a nonempty string that can be divided into two identical substrings, e.g., abcabc. An approximate single tandem repeat is one in which the substrings are similar, but not identical, e.g., abcdaacd. In this paper we consider two criterions of similarity: the Hamming distance (k mismatches) and the edit distance (k differences). For a string S of length n and an integer k our algorithm reports all locally optimal approximate repeats, r = umacro ?, for which the Hamming distance of umacro and ? is at most k, in O(nk log (n/k)) time, or all those for which the edit distance of umacro and ? is at most k, in O(nk log k log (n/k)) time. This paper concentrates on a more general type of repeat called multiple tandem repeats. A multiple tandem repeat in a sequence S is a (periodic) substring r of S of the form r = u(a)u', where u is a prefix of r and u' is a prefix of u. An approximate multiple tandem repeat is a multiple repeat with errors; the repeated subsequences are similar but not identical. We precisely define approximate multiple repeats, and present an algorithm that finds all repeats that concur with our definition. The time complexity of the algorithm, when searching for repeats with up to k errors in a string S of length n, is O(nka log (n/k)) where a is the maximum number of periods in any reported repeat. We present some experimental results concerning the performance and sensitivity of our algorithm. The problem of finding repeats within a string is a computational problem with important applications in the field of molecular biology. Both exact and inexact repeats occur frequently in the genome, and certain repeats occurring in the genome are known to be related to diseases in the human.     

Exact Multiple Comparisons of Three or More Regression Lines: Pairwise Comparisons and Comparisons with a Control

The problem of finding exact simultaneous confidence bounds for differences in regression models for k groups via the union‐intersection method is considered. The error terms are taken to be iid normal random variables. Under an assumption slightly more general than having identical design matrices for each of the k groups, it is shown that an existing probability point for the multivariate studentized range can be used to find the necessary probability point for pairwise comparisons of regression models. The resulting methods can be used with simple or multiple regression. Under a weaker assumption on the k design matrices that allows more observations to be taken from the control group than from the k‐1 treatment groups, a method is developed for computing exact probability points for comparing the simple linear regression models of the k‐1 groups to that of the control. Within a class of designs, the optimal design for comparisons with a control takes the square root of (k‐1) times as many observations from the control than from each treatment group. The simultaneous confidence bounds for all pairwise differences and for comparisons with a control are much narrower than Spurrier's intervals for all contrasts of k regression lines.     

A space-efficient construction of the Burrows-Wheeler transform for genomic data.

Algorithms for exact string matching have substantial application in computational biology. Time-efficient data structures which support a variety of exact string matching queries, such as the suffix tree and the suffix array, have been applied to such problems. As sequence databases grow, more space-efficient approaches to exact matching are becoming more important. One such data structure, the compressed suffix array (CSA), based on the Burrows-Wheeler transform, has been shown to require memory which is nearly equal to the memory requirements of the original database, while supporting common sorts of query problems time efficiently. However, building a CSA from a sequence in efficient space and time is challenging. In 2002, the first space-efficient CSA construction algorithm was presented. That implementation used (1+2 log2 |summation|)(1+epsilon) bits per character (where epsilon is a small fraction). The construction algorithm ran in as much as twice that space, in O(| summation|n log(n)) time. We have created an implementation which can also achieve these asymptotic bounds, but for small alphabets, and only uses 1/2 (1+|summation|)(1+epsilon) bits per character, a factor of 2 less space for nucleotide alphabets. We present time and space results for the CSA construction and querying of our implementation on publicly available genome data which demonstrate the practicality of this approach.