Abstract
An algorithm is described for determining feasibility and calculating parameter values for one or more compound processing orders. Feasibility is determined primarily by applying a series of inequality constraints that result in a valid target concentration range within which orders can be processed. These inequality constraints are obtained from initial compound amounts, source and destination container volume capacities, the liquid handler transfer volume range, and the amount of compound to be processed. If feasible, calculated parameter values include the dilution, transfer and top-off volumes necessary to fulfill the order. Sample code implementing the algorithm is given in Microsoft Visual Basic®d.
Keywords
INTRODUCTION
Caught between the dramatic advances in combinatorial chemistry and high-throughput screening is the increasingly complex task of managing large libraries of compounds. Compound management groups must receive compounds, often from a variety of sources and in a variety of containers. They must transfer and store these compounds, both dry and in solution, and maintain a long-term storage facility. They must respond to a variety of compound requests from their organization. This can include everyone from an individual scientist interested in milligrams of a handful of dry compounds to be distributed in vials, to the ultra high-throughput screening group requiring microliters of hundreds of thousands of presolubilized compounds to be distributed in 384-well or higher density microtiter plates. Sophisticated inventory management software, large automated storage and retrieval robotic systems, and automated liquid handling robots have been introduced to begin to address the problem. 1
One of the primary challenges of such an operation is to find an efficient way to fulfill compound orders. The uninitiated observer might believe that this is a straightforward task, amounting to nothing more than weighing, solubilization of compounds and pipetting. In practice, fulfillment of compound orders is complicated by many factors. These include the texture and composition of the stored substance as well as its solubility in various solvents. The complications introduced by these factors must be addressed on a compound by compound basis.
Additional, often unrecognized complications include the constraints placed on what is possible with diverse storage containers, liquid-handling robots, and compound distribution formats. For example, the concentration to which a container is diluted cannot be lower than what is possible given the working volume of a storage container; any more volume would overflow the container. A second example is the limitation imposed by a liquid handler's transfer volume range. In an effort to achieve maximum efficiency, splitting a single liquid handler transfer into multiple sequential transfers is discouraged due to the extra time required. This results in limitations on the volume that can be transferred in a single step, which, depending on the concentration of the compound in the source container, limits the compound amount that can be transferred to any destination container. A third example is the “dead volume” inherent in a source container. The dead volume is the volume that is left behind in a container due to the fact that it is inaccessible by the liquid handler. This must be accounted for when calculating the amount of compound that can be distributed from a source container. Finally, a destination container has a maximum volume capacity, which limits the amount of volume that it can receive as well as the concentration to which it can be diluted.
Many times compound management groups address the complexity introduced by such constraints by limiting the amount, concentration and format of compounds that are distributed. They may find one set of conditions that works, and operate exclusively under these conditions. Another approach is to use a trial-and-error procedure to find a set of workable conditions for each new compound order. Unfortunately, it may be the case that no workable solution exists. The time spent employing a trial-and-error procedure is wasted. A consequence of constraining the amount, format, solvent or other characteristic of distributed compounds amounts to nothing less than the limitation of the discovery process itself.
What is necessary is a deterministic procedure for dynamically resolving all constraints to determine the feasibility of an order as well as the parameters that define a workable solution for processing compounds. In this paper we describe in detail an algorithm to determine feasibility and parameter values for one or more compound orders. Feasibility is determined primarily by applying a series of inequality constraints resulting in a valid target concentration range. Inequality constraints are derived from arguments of the type described in previous paragraphs. Constraints are obtained from the initial amount of compound available, source and destination container volume capacities, the liquid handler transfer volume range, and the amount of compound to be processed. If feasible, the parameter values that are calculated include the dilution, transfer and top-off volumes necessary to fulfill the order.
A MODEL COMPOUND ORDER
It is assumed that every order fits into a well-defined model. This model order begins with a source container of compound and may include transfers to zero or more destination containers. The amount of compound and volume in the source and destination containers is known. In the case of dry compound, the number of moles is specified with a zero volume. Compounds in solution are specified by a number of moles and a non-zero volume.
A simple order may request that source containers be diluted to a new concentration. If an order includes transfers to destination containers, the amount of compound to be transferred is specified in moles. The final concentration of all source and destination containers also may be specified. If a final concentration is specified, the source and destination containers may require that a topoff volume be added after a transfer is performed to achieve the desired concentration. If the intention is to dry a container as the final step in fulfilling an order, the final concentration is not important.
In summary, an order is modeled as the possible dilution of a source container, followed by zero or more transfers to destination containers, and finishing with a possible top-off of source and/or destination containers. This model will be assumed in the remainder of this paper.
Our model order also assumes that dilution volumes are not subject to the same limitations as transfer volumes. Containers are often diluted with a dispensing device that pumps from a large solvent reservoir. Furthermore, dilution volumes tend to be large and therefore tend not to suffer from lower volume limit constraints.
DEFINITIONS AND CONSTRAINTS
Before proceeding to describe all constraints, we need to define several parameters and variables. These are listed in Table 1.
Variable and parameter definitions used to define constraints.
All constraints were derived by enumerating conditions that would limit processing of one or more compounds, and expressing those limitations as algebraic inequalities. No attempt was made to eliminate superfluous constraints, such as when the satisfaction of one constraint will guarantee the satisfaction of another.
Constraints are divided into two categories, constraints on source and destination container volumes and constraints on target concentration. Any unsatisfied container volume constraint indicates immediately that the order is impossible. Constraints on target concentration will be used to find the range of concentrations within which a source container can be diluted such that transfers can be made to all destination containers to fulfill the requested compound order. If a valid target concentration range is found, all distributions will be possible at any value within that range. An invalid target concentration range (i.e. where the upper target concentration bound falls below the lower bound) is an indication that the order is not feasible. All target concentration inequality constraints are rearranged to isolate target concentration. This will facilitate an application of the algorithm, which is described later.
Constraints are grouped under subheadings by category, where they are described and numbered.
SOURCE CONTAINER VOLUME CONSTRAINTS ON ORDER FEASIBILITY
For a compound order to be feasible, the final volume in a source container, after a top-off must fall below the maximum volume that the container can hold. The amount of compound remaining in a source vessel, after all transfers have been completed, is defined as (SrcInitAmt - ΣXferAmt(I)). Using this expression, the final volume can be calculated using the final concentration as (SrcInitAmt - ΣXferAmt(I))/SrcFinConc. Then, the appropriate constraint on final source volume is as follows.
This constraint should be skipped when an order specifies that the final disposition of a source container is to be dry. In this case the final concentration is infinite and the constraint is automatically satisfied.
DESTINATION CONTAINER VOLUME CONSTRAINTS ON ORDER FEASIBILITY
For each solubilized destination in an order, the amount of compound and the concentration at which it should be dissolved is specified. These values can be utilized to determine how much volume each solubilized destination container must hold. To be possible, the final destination volume for each destination container must fall below the maximum volume that the container is capable of
holding. This constraint is specified algebraically as follows.
This constraint should be skipped for any destination container when an order specifies that the final disposition of the container is to be dry. As with source containers, a dry destination container is essentially at an infinite concentration and therefore the constraint is automatically satisfied.
SOURCE CONTAINER CONSTRAINTS ON TARGET CONCENTRATION
The amount of compound in a source container along with the maximum and minimum volumes that can be held by that container automatically limit the range of concentrations to which the compound in the container can be diluted. The target concentration cannot be smaller than the amount of compound in the source container divided by the maximum volume that can be held by the container. Nor can it be larger than the amount of compound divided by the smallest volume that can be held by the
container. As a result, the following two constraints must be true.
Note that (SrcInitAmt / SrcMaxVol) is the minimum concentration achievable in the source container. And, (SrcInitAmt / SrcMinVol) is the maximum concentration achievable in the source container.
In addition, because dilution only allows concentration to decrease, target concentration cannot be greater than the initial concentration in the source container. As a result, the following
must be true.
Here, (SrcInitAmt/SrcInitVol) is the initial concentration in the source container.
When the initial volume in a source container is zero (i.e. the container is dry), this constraint should be skipped; it is automatically satisfied since initial concentration is infinite.
Finally, if it is required that the remaining compound in the source be diluted further to a specific final concentration, the target concentration in the source container cannot be more dilute
than the final concentration.
SUFFICIENT COMPOUND CONSTRAINTS ON TARGET CONCENTRATION
The next constraint indicates that the source container must have sufficient compound to satisfy all transfers, plus the amount of compound that is inevitably left behind in the source container due to an inability of the pipetting device to access all available
volume. This amount of constraint can be expressed as follows.
(TargetConc × SrcMinVol) is the amount of compound that is left behind in the source container. Rearranging, obtain the following
constraint on target concentration.
PIPETTING DEVICE TRANSFER AMOUNT CONSTRAINTS ON TARGET CONCENTRATION
After dilution, all volumes transferred from the source container must fall within the feasible range of the pipetting device. Volumes to be transferred are a function of the target concentration as well as the amount of compound to be transferred to each destination container.
Therefore, the following two constraints must be satisfied.
(XferAmt(I)/ TargetConc) is the volume to be transferred from the source container using the pipetting device. Rearranging, the
following two constraints on target concentration are obtained.
DESTINATION CONTAINER CONCENTRATION CONSTRAINTS ON TARGET CONCENTRATION
If it is required that a destination be diluted to a specific concentration, then the resulting concentration of the destination immediately after the transfer cannot be more dilute than that destination's final concentration. This is similar to constraint 6 for source containers. The concentration of the destination after the transfer can be represented as the total amount of compound in the container divided by the total volume. Requiring that this is greater than the destination's final concentration yields the following
inequality.
Here, the expression (XferAmt(I)/TargetConc) is the Ith transfer volume. The numerator on the left-hand-side of this inequality is the total amount of compound in the destination container after the transfer. The denominator is the volume in the destination container immediately after the transfer, but before any top-off. Solving for TargetConc, obtain the following constraint.
on target concentration.
DESTINATION CONTAINER VOLUME CONSTRAINTS ON TARGET CONCENTRATION
Destination containers cannot be overfilled or underfilled, as specified by the values of the parameters DestMaxVol(I) and DestMinVol(I). A destination container will be overfilled if the volume transferred into it plus the initial volume in the destination container is greater than the maximum volume allowable. Similarly, it is possible to underfill a destination container if the volume to be transferred plus its initial volume falls below the minimum volume allowable.
The overfill and underfill constraints can be stated algebraically
as follows.
Recall that (XferAmt(I)/TargetConc) is the volume to be transferred to the Ith destination. Rearranging, obtain the following
two constraints on target concentration.
(DestMaxVol(I) - DestInitVol(I)) represents the maximum volume that can be added to the I destination and (DestMinVol(I) - DestInitVol(I)) represents the minimum volume that must be added to the Ith destination.
Constraint 12 should be skipped when the destination's initial volume is equal to or greater than its minimum volume. When equal, the inequality is automatically satisfied since the right hand side is infinite. When initial volume is greater than minimum volume the constraint is not valid, nor is it necessary since it is not possible to underfill the destination.
CONTENTS TRANSFERS
Several constraints listed above are a function of the amount to be transferred to a specific destination container (XferAmt(I)). In these cases transfer amount values are constant. We refer to transfers with constant transfer amounts as “measured” transfers. Occasionally it is necessary to transfer as much as possible from a source container. The amount to transfer is not initially specified. Instead, the order simply requests that as much compound as possible should be transferred. We refer to this as a “contents” transfer. The maximum amount of compound that can be transferred in a contents transfer is the volume in the source container minus whatever must be left behind due to a container's dead volume. The amount of compound left behind is equal to the dead volume multiplied by the target concentration. Unfortunately, target concentration initially is unknown. Therefore, the amount to be transferred in a contents transfer is also initially unknown.
For obvious reasons, a contents transfer should be the last transfer from a source container. We assume that the Nth transfer is reserved for the contents transfer, when one is to be performed. All previous transfers are measured. The amount available for the contents transfer is the initial amount in a container minus the sum of the amount transferred out in measured transfers and the amount that is left behind in the dead volume. This can be
expressed algebraically as follows.
Whenever the final transfer from a source container is a contents transfer, the definition for the transfer amount (XferAmt(N)Contents) should be substituted into the appropriate constraints for the final transfer amount (XferAmt(N)) and the new constraint applied in place of the unsubstituted form. Since the contents transfer amount is a function of target concentration, the newly substituted constraint first must be solved for TargetConc once again before it can be applied.
We will demonstrate how to transform one of the previously given constraints to a form that accounts for a contents transfer. All constraints that are a function of XferAmt(I) will need to be transformed to obtain a complete set of modified constraints that apply to content transfers.
Let's take constraint 8 as our example. The first order of business is to modify the original constraint to apply only to measured transfers. In this case, that involves reducing the number of destinations from N to N-1 since the Nth transfer is reserved for the
contents transfer.
For the contents transfer (where I=N), XferAmt(N)Contents is substituted for XferAmt(I) in the definition of constraint 8 to
yield the following inequality.
Solving for TargetConc, obtain the new contents transfer constraint.
Constraint 8b is not a function of the unknown contents transfer amount, XferAmt(N)Contents. This process can be repeated for all previous constraints that are a function of XferAmt(I) in order to produce a complete set of constraints to be applied when a contents transfer is involved in an order.
A SINGLE SOURCE CONTAINER ALGORITHM
With the given background, the algorithm for testing feasibility and calculating order parameters is quite straightforward. It begins with the compound request, which may be represented in many forms. These include manual entries; text files, including XML and CSV; or database entries. While the method for providing order information is beyond the scope of this paper, a set of preconditions must be satisfied prior to using the algorithm in order to assure that the constraints make sense and that reasonable values are calculated. They are as follows.
SrcInitAmt ≥ 0
SrcInitVol ≥ 0
DestInitAmt(I) ≥ 0, for I=1 to N
DestInitVol(I) ≥ 0, for I=1 to N
XferAmt(I) ≥ 0, for I=1 to N
SrcMaxVol ≥ SrcMinVol > 0 †
XferMaxVol ≥ XferMinVol > 0 †
DestMaxVol(I) ≥ DestMinVol(I) > 0, for I=1 to N †
The first step in the algorithm is to check that constraints 1 and 2 are satisfied. If either is violated, the order is infeasible and the algorithm ends.
If constraints 1 and 2 are satisfied, the next step is to calculate a target concentration range for the source container. This begins by initializing the bounds of the range with known feasible values. Constraints 3 and 4 are useful for this purpose. The lower bound on the target concentration can be initialized using constraint 3 by setting it equal to the result of SrcInitAmt divided by SrcMaxVol. Similarly, an initial upper bound can be calculated using constraint 4 by setting it equal to the value calculated as SrcInitAmt divided by SrcMinVol.
The remainder of the algorithm involves narrowing this initial feasible range using constraints 5 through 12. The current target concentration is tested against each constraint. If a lower bound constraint is violated by the lower bound of the current range, then the range is narrowed from below by an amount sufficient to satisfy the violated constraint. A similar process occurs by testing and adjusting the upper bound.
After all constraints are applied and appropriate adjustments completed, the target concentration upper bound is tested to see if it is still greater than or equal to the lower bound. If this is the case, then the resulting target concentration range is valid. If not, there is no feasible target concentration range that will satisfy all constraints; the order is infeasible and cannot proceed.
Any point within a valid target concentration range can be used to calculate the operating parameters for the compound order. Once the target concentration is selected from a valid range, the volume of solvent to add to the source container to achieve the target concentration can be calculated from the initial state of the source container. Transfer amounts can be used to calculate all transfer volumes. If a final destination concentration is specified, the top-off volume for each destination container can be calculated from the container's final state. Performing these calculations with a target concentration chosen from a valid target concentration range will guarantee that all order parameters will fall within acceptable operating conditions.
Note the strict inequality
EXTENDING THE ALGORITHM TO MULTIPLE SOURCE CONTAINERS
If the same order applies to multiple source containers, it is desirable to make use of multi-channel liquid handling devices, such as 96-channel pipetters, since these devices can increase throughput. Multiple source containers can take the form of multiple vials or microtubes in a rack or multiple wells in a microplate. In this case there is an additional constraint that must be factored into the algorithm; a multi-channel liquid handling device almost always aspirates and dispenses the same volume across all channels at one time.
When there is an identical initial state for all source containers in a rack of tubes or a microtiter plate and when every source has identical destinations, then no difficulty exists since this situation reduces to the single source container case. In other words, if identical source containers are to be processed in an identical manner, then the solution for one source container will apply equally well to all others. When all source containers do not have an identical initial state, or when the order calls for different destinations, a multi-channel liquid handling device can be used in only one step during the fulfillment of an order. It is possible to perform a fixed volume dilution of all source containers using the multi-channel device followed by a variable volume transfer from each source container using some other device. The alternative is to perform a variable volume dilution followed by a fixed volume transfer using a multi-channel liquid handler. Orders that involve straight dilutions only will benefit from a multichannel liquid handler when all source containers have an identical initial state. Our algorithm easily can be extended to solve the case of variable volume dilution-fixed volume transfer. Furthermore, this is the case that can benefit most since an order may call for several transfers, each of which can make use of a multi-channel liquid handler.
To begin the expanded algorithm, constraints 1 and 2 must be applied to all source containers as if they were being processed one at a time. A violation of either constraint will indicate that the order cannot be fulfilled from the failed source container. Upon consideration, one can readily see that the goal of the variable volume dilution applied to a set of source containers is to dilute each container to a constant target concentration over all containers. Once a constant target concentration is achieved, it is possible for a multi-channel pipetting device to be used to simultaneously transfer compounds.
What remains to be determined is the target concentration that simultaneously satisfies all constraints on all source containers. The way to solve for this concentration is first to apply the single source vessel algorithm to each source container in order to obtain a set of valid target concentration ranges, one for each source. Then, this set of ranges is compared to find the largest subset that is common to all. If a valid subset can be found, then diluting each source container to a constant concentration value within this target concentration range subset will guarantee that a multi-channel liquid handling device can be used for all transfers to destination containers as part of fulfilling the order.
There are other ways in which the algorithm can be expanded to account for the realities of compound order processing. For example, akin to the dead volume of source containers, the transfer of liquids often is associated with a volume loss. Furthermore, this loss is frequently a function of the amount of volume that is being transferred. To account for transfer volume loss it is necessary to substitute the constant term XferAmt(I) in all constraints with an appropriate expression. This new expression likely will be a function of TargetConc, requiring all substituted constraints to be algebraically manipulated once again to isolate the TargetConc term. Unfortunately, in some cases the substitution causes the constraint to become quadratic in the TargetConc term. But, a little algebraic elbow grease will yield an appropriate solution.
CONCLUSION
Determining the dilution, transfer and top-off volumes necessary to fulfill a compound order does not have to come down to the establishment of one set of conditions under which all orders are processed, or a trial-and-error procedure that may or may not yield a solution. As outlined by this paper, it is possible to derive a well defined, deterministic algorithm that calculates whether or not an order is feasible, and if so, the range of conditions under which it can be fulfilled.
The basis for such an algorithm is a series of inequality constraints that must be satisfied simultaneously. Constraints are derived from the properties of the compound order, source containers, destination containers, and pipetting devices. Constraints that are a function of target concentration are used to systematically narrow an initially feasible range. If a valid concentration range results after all constraints are applied, then the order is feasible. Furthermore, any target concentration value within a valid range can be used to calculate all other processing parameters and lay out a direct method to fulfill the order. A sample implementation of the algorithm is given in the Visual Basic® computer language.
The algorithm can be extended in a variety of ways. A method was outlined for extending it to include the simultaneous processing of multiple source containers, as would be the case with a multi-channel pipetting device. It is also possible to extend the algorithm to treat orders that include contents transfers, for which the exact transfer amount may not be known beforehand, or to account for other complications, such as the volume lost in pipette transfers. An example was given detailing how to algebraically manipulate the appropriate constraints to include contents transfers. An expanded form of the algorithm currently is being used as part of the Bristol-Myers Squibb compound ordering system.
Footnotes
APPENDIX: AN IMPLEMENTATION OF THE ALGORITHM IN VISUAL BASIC®
This section contains an implementation of the feasibility algorithm written in Visual Basic®. The algorithm is initiated by calling the ProcessOrder function. The user-defined type Data and the values contained in dblXferMaxVol and dblXferMinVol are then passed to the VerifyOperation function, where feasibility is determined. This is accomplished by applying each applicable constraint to narrow the feasible concentration range. After each constraint is applied, the concentration range is verified to ensure validity. If the result of VerifyOperation indicates that the order is feasible, the remainder of the ProcessOrder function is executed to calculate the specific volumes that can be used to fulfill the order. These are returned to the calling application as values of the remaining parameters passed to ProcessOrder.