In order to identify the infected individuals of a population, their samples are divided in equally sized groups called pools and a single laboratory test is applied to each pool. Individuals whose samples belong to pools that test negative are declared healthy, while each pool that tests positive is divided into smaller, equally sized pools which are tested in the next stage. In the$(k+1)$-th stage all remaining samples are tested. If$p< 1-3^{-1/3}$, we minimize the expected number of tests per individual as a function of the number$k+1$of stages, and of the pool sizes in the first$k$stages. We show that for each$p\in (0, 1-3^{-1/3})$the optimal choice is one of four possible schemes, which are explicitly described. We conjecture that for each$p$, the optimal choice is one of the two sequences of pool sizes$(3^{k} \text {or }3^{k-1}4,3^{k-1}, {\dots },3^{2},3)$, with a precise description of the range of$p$’s where each is optimal. The conjecture is supported by overwhelming numerical evidence for$p>2^{-51}$. We also show that the cost of the best among the schemes$(3^{k}, {\dots },3)$is of order$O\big (p\log (1/p)\big)$, comparable to the information theoretical lower bound$p\log _{2}(1/p)+(1-p)\log _{2}(1/(1-p))$, the entropy of a Bernoulli$(p)$random variable.

BACKGROUND: Many algorithms exist for protein structural alignment, based on internal protein coordinates or on explicit superposition of the structures. These methods are usually successful for detecting structural similarities. However, current practical methods are seldom supported by convergence theories. In particular, although the goal of each algorithm is to maximize some scoring function, there is no practical method that theoretically guarantees score maximization. A practical algorithm with solid convergence properties would be useful for the refinement of protein folding maps, and for the development of new scores designed to be correlated with functional similarity. RESULTS: In this work, the maximization of scoring functions in protein alignment is interpreted as a Low Order Value Optimization (LOVO) problem. The new interpretation provides a framework for the development of algorithms based on well established methods of continuous optimization. The resulting algorithms are convergent and increase the scoring functions at every iteration. The solutions obtained are critical points of the scoring functions. Two algorithms are introduced: One is based on the maximization of the scoring function with Dynamic Programming followed by the continuous maximization of the same score, with respect to the protein position, using a smooth Newtonian method. The second algorithm replaces the Dynamic Programming step by a fast procedure for computing the correspondence between C alpha atoms. The algorithms are shown to be very effective for the maximization of the STRUCTAL score. CONCLUSION: The interpretation of protein alignment as a LOVO problem provides a new theoretical framework for the development of convergent protein alignment algorithms. These algorithms are shown to be very reliable for the maximization of the STRUCTAL score, and other distance-dependent scores may be optimized with same strategy. The improved score optimization provided by these algorithms provide means for the refinement of protein fold maps and also for the development of scores designed to match biological function. The LOVO strategy may be also used for more general structural superposition problems such as flexible or non-sequential alignments. The package is available on-line at http://www.ime.unicamp.br/~martinez/lovoalign.

Fortran 77 software implementing the SPG method is introduced. SPG is a nonmonotone projected gradient algorithm for solving large-scale convex-constrained optimization problems. It combines the classical projected gradient method with the spectral gradient choice of steplength and a nonmonotone line-search strategy. The user provides objective function and gradient values, and projections onto the feasible set. Some recent numerical tests are reported on very large location problems, indicating that SPG is substantially more efficient than existing general-purpose software on problems for which projections can be computed efficiently.