search

HPInc / HP-Digital-Microfluidics

HP Digital Microfluidics Software Platform and Libraries
MIT License
3 stars 1 forks source link

Add mixing operations #21

Closed EvanKirshenbaum closed 10 months ago

EvanKirshenbaum commented 10 months ago

I'm adding this as an issue (rather than just having it be part of #2), in order to be able to capture my notes/thoughts on two aspects to this problem, which I'll cover in separate comments:

  1. How do you deal with the fact that a mixing operation takes n inputs and produces n outputs, each of which has their own incoming and outgoing paths?
  2. How do you actually do the mixtures of n reagents to get essentially equal proportions (say, within 10%), given that you can only actually do pairwise (or, perhaps, 3-way) mixing?
Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 13, 2021 at 4:45 PM PDT. Closed on Jul 09, 2021 at 5:50 PM PDT.
EvanKirshenbaum commented 10 months ago

This issue was referenced by the following commits before migration:

EvanKirshenbaum commented 10 months ago

For the first problem (dealing with multiple paths), I have come up with four possible solutions. The first three are ugly:

  1. One path goes through a MixOp, which takes an Event as a parameter. The other path (or all the other paths) add an operation that waits on this event.
    • One problem with this is that you have to be able to identify the other drops to mix with. With only two, you can provide a direction and hope that there's exactly one other drop in the neighborhood of that neighbor. With more than two, it becomes more complicated.
    • Another problem is that you have to provide the event somewhere. With all other operation arguments, you bind it in as an attribute of the operation object, but that doesn't work with an Event if you want the operation to be performed multiple times (perhaps, even, simultaneously).
  2. The Mix2Op operation similarly notes its other drop, but the other drop's path ends there. The operation produces a Delayed[tuple[Drop,Drop]]. We then pass through a ForkOp[Drop,Drop]. which is created with a complete operation sequence to use for the secondary drop and returns the primary drop to continue on.
    • The main problem with this is that you need to know where you're going to go with the second drop before you create the fork, although there might be a way to create it and then update it later. (This would have problems if somebody tried to go down different paths at different times.)
  3. Somehow Mix2Op returns a tuple of futures (rather than a future of a tuple), and you do something like 
    d1_future, d2_future = ...then(Mix2Op()).schedule()
d1_future.then_schedule(...)
d2_future.then_schedule(...)
    • This is ugly, as it doesn't allow you to create the entire path for any drop, but forces you to break on the scheduling and schedule the results directly.

The fourth solution is more elegant, although there is still some awkwardness. The basic idea is that you create a MixingPoint object (not an operation) that knows how many drops will participate and, optionally, how many shuttles to perform. Each drop's path goes through an InMixOp operation, which knows the MixingPoint and, possibly, which drop it is in the dance. The MixingPoint has a tuple of drops, and each InMixOp posts to the appropriate one and waits on an Event in the MixingPoint. When the last drop joins, the InMixOp runs the dance and then signals the event.

There are several advantages to this:

  1. Each drop gets its own path, both before and after the mixing, so several mixtures can take place along the same path.
  2. The drops don't all need to get to the rendezvous at the same time. The early ones will wait for the laggards.
  3. The drops identify themselves, so they don't have to identify the middle cells by direction.
  4. A single MixingPoint class can be used for any number of drops participating in the mixture, with different dances used for each. The class can also be written to handle multiple orientations.

The main disadvantage is that the MixingPoint needs to be constructed out of band, which makes it harder to reuse it for multiple paths (either simultaneously or later on).

One possible solution for this is for the InMixOp to take a key rather than the MixingPoint itself. When the first drop gets to an InMixOp with that key, the MixingPoint is created and associated with the key. When it's done (or as soon as all the drops arrive), it is unregistered. This will allow the same key to be used at different times, although not simultaneously. I'll have to think about this some more.

Okay, thinking about it some more, it may be possible to leave out the keys altogether (or at least make them optional). If The InMixOp takes a "k of n" specification, it will probably be possible to determine when you've gotten n (in n different slots) that could conceivably go together and start there. I'm not sure that that handles all of the cases (e.g., what happens when you have A and B mixing and C and D mixing, but B and C are the first ones there and they're close enough to trigger?) We may need a bit more, but that seems like a good start. Maybe some description of the bounding box from the first one? (i.e., the one in slot zero).

The more I think about it, the more I like the idea of specifying the bounding box (west and then south) from drop zero). I was toying with the idea of having each one pick the direction of the next, but that doesn't give us the notion of the area we have to play in. Alternatively, we could use the last direction to ensure that we at least have three spaces in both directions. Alternatively alternatively, we could have constants for various starting patterns and bounding boxes.

This still raises the question of how we make sure that all of the paths agree on their parameters, but that's probably okay, since they also have to make sure they get to the right positions. I guess we could obviate having to specify it in each place if only drop zero has to specify, since the other drop positions would be inferable from it.

Also, it's probably better to use a future than an event to signal the end of the mixture. Each drop, when it gets there, either gets a future from the MixingPoint and adds a callback to post itself on its own future or (probably better), just hands its own future to the MixingPoint, which posts the drop to it when it's done.

Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 13, 2021 at 5:18 PM PDT.
EvanKirshenbaum commented 10 months ago

As to how to mix n drops evenly with only pairwise mixing, here's what I have. In the following, A, B, C, etc., are drops. AB, etc., are pairwise mixtures (that result in each participating drop having the same concentrations).

First off, for powers of two, it's straightforward. With two drops, you just mix AB. With four, you mix AB and CD, and then you mix AC (and, if you want more than two resulting drops, BD).

In general, if you have 2n drops, you can split them in half, mix each half (of size n) together, and then mix the resulting drops across the halves (either one of each or line them up and mix corresponding drops).

The trickiness comes when you have an odd number of drops (especially a prime number).

In the following tables, each successive line should be read as the proportion of initial reagents, with the number being the numerator, and the denominator being the sum. Each row necessarily has k pairs (which participate in the mixing at that step) and one single (which doesn't).

3 drops

step pair conc drop conc
1 AB 1,1,0 C 0,0,2
2 BC 1,1,2 A 2,2,0
3 AB 3,3,2 B 2,2,4
4 BC 5,5,6 A 6,6,4
5 AB 11,11,10 C 10,10,12

This gets AB to under 10%. Each remaining step essentially cuts it in half, so one more step will suffice to get all three drops there.

The basic notion is that you line the three drops up and bounce the middle one off the other two in sequence.

5 drops

For five drops, you treat the drops as though they are in a circle and rotate the odd one out around the circle. (This will also work for three drops, in the same number of steps, but it may mean more motion).

step pair conc pair conc drop conc
1 AB 1,1,0,0,0 CD 0,0,1,1,0 E 0,0,0,0,2
2 BC 1,1,1,1,0 DE 0,0,1,1,2 A 2,2,0,0,0
3 CD 1,1,2,2,2 EA 2,2,1,1,2 B 2,2,2,2,0
4 DE 3,3,3,3,4 AB 4,4,3,3,2 C 2,2,4,4,4
5 EA 7,7,6,6,6 BC 6,6,7,7,6 D 6,6,6,6,8
6 AB 13,13,13,13,12 CD 12,12,13,13,14 E 14,14,12,12,12

7 drops

With 7 drops, you start out the same way:

step pair conc pair conc pair conc drop conc
1 AB 1,1,0,0,0,0,0 CD 0,0,1,1,0,0,0 EF 0,0,0,0,1,1,0 G 0,0,0,0,0,0,2
2 BC 1,1,1,1,0,0,0 DE 0,0,1,1,1,1,0 FG 0.0.0.0.1.1.2 A 2.2.0.0.0.0.0
But then you need to go across for a couple of steps to even things up and ensure that everybody has a non-zero bit of each: step pair conc pair conc pair conc drop conc
3 BF 1,1,1,1,1,1,2 AD 2,2,1,1,1,1,1 EG 0,0,1,1,2,2,2 C 2,2,2,2,0,0,0
4 AE 2,2,2,2,3,3,2 CG 2,2,3,3,2,2,2 BD 3,3,2,2,2,2,2 F 2,2,2,2,2,2,4
And then you can go around the circle again: step pair conc pair conc pair conc drop conc
5 EC 4,4,5,5,5,5,4 GB 5,5,5,5,4,4,4 DF 5,5,4,4,4,4,6 A 4,4,4,4,6,6,4
6 CG 9,9,10,10,9,9,8 BD 10,10,9,9,8,8,10 FA 9,9,8,8,10,10,10 E 8,8,10,10,10,10,8
7 GB 19,19,19,19,17,17,16 DF 19,19,17,17,18,18,18 AE 17,17,18,18,20,20,18 C 18,18,20,20,18,18,16
8 BD 38,38,36,46,34,34,34 FA 36,36,35,35,38,38,36 EC 35,35,38,38,38,38,34 G 38,38,38,38,34,34,32

which leaves FA with an 8.6% error.

9 drops

I haven't worked out a precise dance for 9 drops, but there's an upper bound of 10 steps:

  1. Split the drops into three groups of three
  2. Mix the three drops in each group (5 steps).
  3. Mix representatives from each of the three groups (5 steps).
Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 13, 2021 at 5:33 PM PDT.
EvanKirshenbaum commented 10 months ago

Continuing with the first question (and starting a new comment, because the other one was getting long):

I'm starting to lean toward yet another option. To wit:

Thinking about it more, I think it's probably better to have preset objects that encapsulate

The actual flow could look something like this.

Assume a 3-way mix between A, B, C. A is the lead drop. To show all facets, assume they execute their operations in the order B, A, C.

  1. B executes InMixOp while sitting on pad PB.
    1. It checks lead_first[PB] to see if anybody is waiting for it.
    2. The result is None, so nobody is.
    3. It puts its own future as secondary_first[PB].
    4. It is now done. The mixing operation will post its future.
  2. A executes MixWithOp while sitting on pad PA.
    1. It knows that it will mix with drops at pads PB and PC.
    2. It checks secondary_first[PB] and secondary_first[PC] to see if either got there before it.
    3. It sees a future at PB, but not at PC.
    4. It creates a local mapping of A to its own future and B to the future it found.
    5. It clears secondary_first[PB].
    6. It then installs a function at lead_first[PC] that knows that knows that it needs one more drop.
    7. It is now done. The mixing operation will post its future.
  3. C executes InMixOp while sitting on pad PC.
    1. It checks lead_first[PC] to see if anybody is waiting for it.
    2. There is a function there, so it calls it, passing in C and its future.
    3. The function
      1. installs C and the future in the local mapping.
      2. clears lead_first[PC].
      3. decrements the number of drops waited for.
      4. Notes that the number is zero, and so
        1. runs the mixing protocol
        2. posts each drop to its respective future.
Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 14, 2021 at 3:39 PM PDT.
EvanKirshenbaum commented 10 months ago

2-, 3-, and 4-way mixes work and have a wombat-tool driver. I'm going to put this on hold until I get the pie-chart display (#15) working.

One note: I currently have each mix type present a script of pairwise mixes and, perhaps, walks, that happen at each step (with each taking a merge and a split and repeated for a number of shuttles). Each step updates errors on drops, and we continue until all drops that care get down to their desired tolerance.

I just realized that for an 8-drop mix, if you just want drop A mixed, you can start as

D A B C
E F G H

and then mix

  1. DA, BC, EF, GH
  2. AB, FG
  3. AF

but then you're going to have to walk things so that DC and EH (or DH and EC) can mix.

Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 18, 2021 at 10:05 AM PDT.
EvanKirshenbaum commented 10 months ago

It dawned on me (way, way too early) this morning that the script-based approach to mixing isn't quite general enough. It works fine for up to five reagents, but when you get to six, it breaks down.

The reason is that I'm currently treating a script as a list of steps, each having a set of actions, each mixing 2 drops and reporting the resulting error. We walk through the steps until every drop's error matches its tolerance.

For 6-way mixing, what we want to do is to split the six drops into groups of 3 (in parallel lines), mix each to the appropriate tolerance, and then mix across the lines. But if we do it honestly, the first stage will never terminate (since the errors will always be infinite), and if we lie and only pretend to care about within-group mixing, it will decide to terminate as soon as the first stage is done.

(It occurs to me that in this case, we can get around this by doing the 2-way mixes first, since they are perfect, but we'll still hit this problem with 9, which wants to be done as 3x3.)

I can see two ways to approach this:

  1. Somehow treat 6-way mixing as two 3-way mixes and 3 2-way mixes.
    1. This is probably the cleanest way to do it if I can figure out how, as it will make generalizing easier.
    2. We will need some way to ensure that everybody's in position for the next set of mixes. (This won't be a problem here, but it will be if we decompose 10 into 2x5.) This should probably be an overall guarantee so that what follows a mix doesn't change if tolerances change.
    3. We will need synchronization after each phase so that drops that finish early don't start walking away, assuming that those that are still mixing aren't in their way.
  2. Make the script explicitly have multiple stages. In each stage, have all the mixes (in all groups), but report errors only for that group. After each stage, reset the set of unsatisfied drops.
    1. This has the same alignment and synchronization issues as the other option.
      Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 19, 2021 at 1:20 PM PDT.
EvanKirshenbaum commented 10 months ago

Building on that last comment, it looks as though what I want to is have primitive scripts and composite scripts. A primitive script runs through a number of steps, as I currently have it, while a composite script has phases, each of which has a MixingType and an anchor point.

For example, with a 6-way mix having drops

0 1 2
3 4 5

with the major direction across and the minor down (i.e., created as Mix6(major, minor)),

I think we can run each of a phase's sub-mixes to completion, including setting ones we don't care about to waste_reagent (but not setting ones we care about to the final result), and we can probably simplify by saying that if everything (or, possibly even if just the lead drop) is already waste, we can skip the mix. But it doesn't really cost anything, so it may not be worth it.

Note: When figuring termination for each phase, we have to be careful. Done naively, a 9-way mix to 10% (as 3, 3-way mixes) would result in a drop of

121, 121, 110, 121, 121, 110, 110, 110, 100

which would actually be a 21% error. I think that the right thing to do is to distinguish between perfect mixes and approximate mixes. When figuring the required tolerance for a drop, we want to take the nth root of the (1 plus) the requested tolerance, where n is the number of approximate mixes. In this case, we take the square root of 1.1 and get 1.0488, so we need to stop on a 4.88% tolerance. Running that, we get

1,849, 1,849, 1,806, 1,849, 1,849, 1,806, 1,764, 1,764, 1,848

which is a 4.82% error overall.

Yes, this is overkill, but in working through this, I noticed a problem. If I run the three-way merges one step further than usual, it results in 21:21:22, on the other drops, but only 22:22:20 (i.e., 11:11:10) on the lead, because the lead drop doesn't participate in that step. This means that if we went one more step in a 9-way mix, we would have drops of

441, 441, 462, 441, 441, 462, 462, 462, 484

with an error of 9.75%, but to use that we would have to re-designate which is the lead, which would make things difficult for further processing. (Unless it turns out we can always figure out the best lead drop, in which case a mix might just involve a jump in position. E.g., after a three-way mix, the lead drop is always in the middle.) I think it's probably best to just do the extra steps and get higher precision.

Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 20, 2021 at 11:19 AM PDT.
EvanKirshenbaum commented 10 months ago

Further notes:

EvanKirshenbaum commented 10 months ago

Pure and composite mixes appear to work, including the tolerance adjustment I've tried it with 6-way and 9-way, at least.

Note that the wombat tool "walk to well sequence" is still not quite right, as it gets the drops too close together when trying to get into the well. I may need to try to find a more general solution. This notion of trying to work out the timing on paper is a real pain (and, obviously, error-prone).

Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 21, 2021 at 6:15 PM PDT.
EvanKirshenbaum commented 10 months ago

Thinking a bit about 8-way mixes. With the current framework, they're a bit trickier than I'd like, especially for a perfect power-of-two mix.

The obvious approach is to start things off

A B C D
E F G H

Then mix the two lines and mix each outer pair with its neighbor. This yields two squares of four drops, ABEF on the left, CDGH on the right. If you then mix the middle, you get four perfectly mixed drops.

But not the lead drop, if that's A. And not all of them if you care.

There are a couple of ways I can deal with this:

  1. I can make the lead drop be one of the middle positions. This gets us there if we only care about it, and I can short circuit, and I can short-circuit any of the full-mix approaches if we only need one drop.
    • Honestly, I think that the only reason I'm avoiding this is that I put a lot of time into the wombat tool mix paths, and this breaks them.
  2. I can say that I don't guarantee drop identity coming out of a mix, and I don't guarantee that it's in the original position.
    • This would mean that I just post B to A's future.
    • But it means that nobody outside can cache the drop, and you can't be sure after a mix where you're going to come out.
      • Unless it's a property of the mix type where each drop comes out.
      • In any case, it still screws up the wombat task.
  3. I can do a full mix by walking the drops:
    • When I mix the middles together, I walk the outside ones up or down.
    • Then I walk them to the middle
    • Then I mix them together
    • Then I walk them out
    • Then I walk them down
      1. There are two downsides to this:
      2. First, it adds another 4 steps to the mix, for a total of 7, These steps are arguably unnecessary.
      3. Second, it requires four rows of drops. This will be a problem on wombat, which can't do 4x4
  4. I can get just A (and C) in 7 steps using just 3 rows:
    • After the first two mixes, move B up.
    • Then move C toward A.
    • Then mix A and C. A is now fully mixed.
    • Then move C back toward D.
    • Then move B back down.
      1. If I don't care about the original positions of the other drops, I can stop after the third extra step (step 5). If I don't care about identity, but I do care about original position, when I mix A and C, I can move B to the right and then down on the next step. This leaves me with 
        A C B D
E F G H

        in 6 steps, and I can post C to B's future and vice versa.

Migrated from internal repository. Originally created by @EvanKirshenbaum on Jun 22, 2021 at 10:14 AM PDT.
EvanKirshenbaum commented 10 months ago

Closing this. See. https://github.com/HPInc/HP-Digital-Microfluidics/issues/30 [comment by @EvanKirshenbaum on Jul 09, 2021 at 5:47 PM PDT]

Migrated from internal repository. Originally created by @EvanKirshenbaum on Jul 09, 2021 at 5:50 PM PDT.