Dichotomous search

Dichotomic search for unknown ligand from cocktail 1. The number of compounds in the sub cocktail is indicated by n, and the interpretation about the presence of compound X in the subcocktail is given as Y/7/N. 

For trypanosomal TIM we experimented with three different cocktails of 32 compounds (Table 4). Molecules were chosen in such a way that they would be compatible, soluble, cheap, and as varied as possible. Each compound was present at a concentration of 1 m M The final cocktail solutions were clear and devoid of precipitate. Since this was a pilot experiment both subcocktails were checked at each stage of the dichotomic strategy. Only the soak with cocktail 1 revealed electron density that could not be accounted for by water molecules, hereafter called peak X. The soaks with cocktails 2 and 3 led to featureless difference Fourier maps. The quality of the data and refinement can be inspected from Table 5, while Figure 9 illustrates the dichotomic search to identify peak X. An oxidized molecule of DTT, identified in the high-resolution structure of the native TIM crystals [24], served as an internal reference to judge the quality of the data and the noise level in the final difference Fourier maps. 

Consider the sequential extension of the dichotomous search. After the first pair of experiments the new interval to be searched is only half as long as the original one. This new interval can be halved again by... 

Thus the sequential dichotomous search is considerably more powerful than the preplanned uniform dichotomous search, the advantage growing exponentially with the number of experiments. To reduce the interval of uncertainty to 1% of the original would require 200 preplanned dichotomous experiments. The same job could be done with only 14 sequential dichotomous experiments. 

The last cycle of the method will be a dichotomous search, which we know is minimax for two experiments. Keifer (Kl) and Johnson (J2) show that the Fibonacci search is in fact minimax among all sequential techniques. In order to reduce the interval of uncertainty to less than 1% it only takes 11 Fibonacci experiments, three less than for a sequential dichotomous search. The advantage increases with the number of experiments. 

So far we have only discussed methods where the number of experiments, or equivalently, the size of the final interval desired, is known in advance. It often happens, however, that the experimenter does not decide in advance how many trials to perform. He just keeps trying until satisfied. If a dichotomous search is used, the sequence does not depend on the ultimate number of experiments, since at each stage the remaining interval is bisected. On the other hand, the exact location of the first two Fibonacci trials in principle depends on n, the total number of experiments to be performed. Fortunately, the ratio F -2/Fn is very near its limit 0.38 for n greater than 4. A very nearly optimal Fibonaccian method would be to take... 

Dichotomous search, 407 Dimensionless numbers, definitions of 468-469 DIPPR, 117 Direct costs, 210 in capital investmenf 167 Direct production costs, 197-204,210 Discounf definition of, 226 Discount factors definition of 223/i 236-237, 303 tables of 219, 234-235, 240-246... 

Other line search methods that involve only function evaluations, that is, no derivative calculations, are the dichotomous search, the Fibonacci search (Kiefer 1957), and the quadratic fit line search. The Fibonacci search is the most efficient derivative-free line search technique in the sense that it requires the fewest function evaluations to attain a prescribed degree of accuracy. The quadratic fit method... 

---