Tests: unit tests for parts algorithm

[vsoch]

We currently use an algorithm to allow for a user to provide a sequence and then query the API for parts, cache the query, find all forward/reverse part sequences in the query sequence, and then use a scheduling algorithm to sort the list and (starting with the longest) add part sequences to the query that don't overlap. Complete details are in this comment: vsoch/freegenes#63 (comment)

I tested basic cases (manually assembling a part) and we would need unit tests to ensure that (most) use cases that are possible return correctly (as we would want/expect). To do this, the unit tests shouldn't rely on the API, but instead can add a loaded json of output from the API, provided here:

parts.json.txt

To the client, meaning like:

from freegenes.main import Client

# Don't check for token
client = Client(validate=False)

# Load the json data here (parts), add to the cache
client.cache['parts'] = parts

# Then test the function to return sequences from some query sequence
selected_parts = self._derive_parts(sequence)

The above should all be possible without needing to interact with API endpoints / tokens (and reasonable for unit testing).

As a logged in user, you can see the create endpoint here and the function for the client to interact is documented here. @shea256 would this be something you'd like to work on, if you are interested in the genomics side of things too? I think @Koeng101 could give you guidance about the kinds of testing cases that we would want.

[shea256]

Hey @vsoch yes I am interested in this and in the genetics side generally. I will take a closer look and get back to you shortly before I commit to this one, but looks good so far.

[vsoch]

Cool! And if/when you learn (biology related) stuffs, please teach me too :)

[shea256]

Sure thing, will do! And the same for you too please :)

[vsoch]

If you want more unnecessary detail, I wrote this up yesterday here -> https://vsoch.github.io/2019/composite-parts/

[vsoch]

For future folks reading the issue, see the final tail of discussion in the "CompositePart API Integration" link above. Further discussion will continue here, as it pertains to the algorithm in this library.

[shea256]

Continuing the conversation from vsoch/freegenes#63...

@vsoch wrote:

@shea256 yes it could definitely be the case that the list of parts includes some higher level parts, and then smaller constituent parts. The question (probably for @Koeng101) is which should be represented for the Composite Part. Or if more than one should (this gets messy fast). Regardless of this decision, the path forward is fairly logical, here is what I would do:

• first review the algorithm with @Koeng101 - I came up with it without much biology background and short conversation with Keoni, so it definitely could need some tweaking. For example, as we just discussed, it could be that the longest parts aren't the "best" but some other metric is.
• work with @Koeng101 to develop a set of "gold standard" test cases. I've provided the base part data to add with the repository for this case.

Yes I agree that we should review the algorithm with @Koeng101 and get his feedback here, as well as develop a quality set of test cases.

My instinct is the system is going to be fairly similar to the iGEM parts catalog (http://parts.igem.org/Catalog).

The small constituent parts are what will need to be surfaced: promoters, terminators, coding regions, etc.

Consider this example here: http://parts.igem.org/Part:BBa_I13520

This part has:

• a promoter
• a ribosome binding site
• a protein coding sequence
• 2 terminators

Correct me if I'm wrong @Koeng101, but there could theoretically be a part without the second terminator, or a part without the promoter.

For someone who wants to see what is "inside" this composite part, you'd want to see all of the meaningful units - the promoter, the ribosome binding site, the protein coding region, and the two terminators. You wouldn't want to see a promoter, a composite, and then a terminator.

@vsoch wrote:

Given the test cases and the list of "gold standard" criteria, this should be enough to guide development, and then verify if everything works as expected with the unit tests. If there are any changes needed to the server (e.g., if you decide to maintain all possibilities for a composite part from a new sequence, what does that mean for the post?) please outline with the changes so I can make them and test against your updated freegenes-python locally. Of course you could do this too! Thanks for your thoughts @shea256! Could you please move discussion to #8 since this is where development will be happening?

Makes sense! If there are any changes need to the server, I will outline the changes.

[vsoch]

Great! Let's give Keoni some time to think and respond - it's 6:30am over there in California! 🌞

[shea256]

Following up on my iGEM catalog example - this is actually a better one:

http://parts.igem.org/Part:BBa_K769022

Promoter, RBS, Coding Sequence, Terminator, Terminator, Promoter, RBS, Coding Sequence, Terminator, Terminator

This shows how parts can even have multiple complete composite parts within them (the two coding sequences are each wrapped in promoters, RBS's and terminators).

@Koeng101 wrote on vsoch/freegenes#63:

The main reason I ask for this is because we're going to need to update ALL samples, and each composite is probably going to have on order ~10 parts. If I was just selecting from a list, that's going to be about 10,000 search + clicks.

Based on this requested interface, it might be useful to tell the user:

We found these promoters, ribosome binding sites, coding regions, and terminators
Please confirm the parts

Other than doing subset search on sequences, it also might be useful to look for context clues within the DNA like start and stop codons.

This could allow us to know where the coding regions are and where the promoter and terminator regions are.

Then there could be localized priority queues where each coding region has its "best guess" match and each promoter, terminator, etc. has its own best guess match and then a longer list of alternatives, just in case the search didn't make the right first guess.

@vsoch wrote:

Great! Let's give Keoni some time to think and respond - it's 6:30am over there in California! 🌞

And sounds good, just wanted to provide a few more thoughts I had on this before moving on :)

[shea256]

OK one more last thought, promise :)

It might be useful to have a distinction between how the composites are represented in the database and how the composite constituent parts are displayed.

For non-redundancy in the database, it sounds like it would be useful to have a hierarchy of composite parts, if it is in fact true that the composites are built up this way.

For showing the constituent parts visually, you'd probably want to show the full hierarchy. You'd want to allow people to see each of the promoters, terminators, etc. and you'd want people to see what commonly used composites were combined to produce a composite composite.

Thus, the representation in the database might look as follows:

• Lux + GFP Composite
  • Lux Operon Composite:
    • Promoter
    • RBS
    • Coding Sequence
    • Terminator
    • Terminator
  • GFP Composite:
    • Promoter
    • RBS
    • Coding Sequence
    • Terminator
    • Terminator

But @Koeng101 will set the record straight for us and let us know if we're on the right track or not.

[Koeng101]

My instinct is the system is going to be fairly similar to the iGEM parts catalog (http://parts.igem.org/Catalog).

Ding ding ding! You are correct!

For someone who wants to see what is "inside" this composite part, you'd want to see all of the meaningful units - the promoter, the ribosome binding site, the protein coding region, and the two terminators. You wouldn't want to see a promoter, a composite, and then a terminator.

Yes, that is correct. There are some cases in which that might not be true (you may want an optional view of higher level composites) but that's pretty far out in the future.

Then there could be localized priority queues where each coding region has its "best guess" match and each promoter, terminator, etc. has its own best guess match and then a longer list of alternatives, just in case the search didn't make the right first guess.

To extend on this idea, different parts can have different filters - like it might be ok if an promoter is 37 base pairs, but we wouldn't accept a CDS that is 37 base pairs (It's not divisible by 3)

For non-redundancy in the database, it sounds like it would be useful to have a hierarchy of composite parts, if it is in fact true that the composites are built up this way.

I've thought pretty deeply about this topic. As put above, there is the idea in synthetic biology of "devices" that I think was first put forward by Drew in 2003 - this is a quote from the paper:

Standard parts can be defined prior to absolute scientific knowledge; many
knowable facts are unnecessary. Simpler representations of many-component
devices help to manage complexity and increase attainable system scale.

HOWEVER: This was a while ago, and there is a better way (I think), which I like to call an "architecture".

A composite-composite would be the following:

• Lux + GFP Composite
  • Lux Operon Composite:
    • Promoter
    • RBS
    • Coding Sequence
    • Terminator
    • Terminator
  • GFP Composite:
    • Promoter
    • RBS
    • Coding Sequence
    • Terminator
    • Terminator

But an architecture would be:

• A Lux + GFP Composite
  • A Lux Operon Composite:
    • A Promoter
    • A RBS
    • THIS Coding Sequence
    • A Terminator
    • A Terminator
  • A GFP Composite:
    • A Promoter
    • A RBS
    • THIS Coding Sequence
    • A Terminator
    • A Terminator

Why the difference? Simply put, there are many ways to instantiate a "A GFP Composite" - you could use a hundred different promoters, a hundred different RBSs, a hundred different terminators. All are different composite parts (since composite parts will be physically be different) but all are GFP Composites.

The relevance of this is our lack of understanding and incapability to effectively design biology. We know general patterns that give outputs, but we can't really precisely design those. The most effective way, so far, has been to have an outline, and then do a combinatorial or evolutionary approach to get the end product.

Practically, this means that humans would design an architecture that could give an output (which humans are good at), and then give the computer a target output. For example, we humans know that promoter + lead sensor RNA + rbs + GFP + terminator produces GFP in a cell whenever there is lead around. But we want there to be to not be any expression of GFP when there is no lead around, and we want there to be a high expression of GFP when there is lead around. Knowing the general architecture of a GFP lead sensor and variety of parts in our database, our computer then queues assemblies of 1,000 variations of this architecture and data collection runs of those 1,000 variations (THIS is what "Operations" are in the database). After a few rounds, basically just using well established algorithms from computer science, we can arrive at a solution to our desired problem. The data collected from those 1,000 variations is saved and can be used in designing later runs.

These architectures can then be piled on top of each other iteratively, and you can probably imagine that if you chain together architectures, you can eventually arrive at a generically defined cell "architecture" created from hundreds of sub-architectures PLUS a massive dataset of how each composite or subarchitecture works at each level. By continuously learning, perhaps one day we can have people define an "electric mouse", which is compiled into millions of sub-architectures that builds you pikachu. Or something along those lines, a dragon would be cool too.

Of course, we're pretty far out from this state, so I haven't really written all of this down, and just showing all parts in a composite makes sense (we want that kind of tree structure for viewing architectures).

I tested basic cases (manually assembling a part) and we would need unit tests to ensure that (most) use cases that are possible return correctly (as we would want/expect). To do this, the unit tests shouldn't rely on the API, but instead can add a loaded json of output from the API, provided here:

Will try to make today! Will have to drop off edge of map for a couple hours though, Hannah and I are leading lab meeting in 2 hours and have completely not prepared anything.

[vsoch]

The vision is really great! But for now, let's not lose sight of the current scope - we are adding CompositeParts (in their simplest form), the idea being to build up to this vision. But we have to start simple - so all of the above is great, but it needs to be carefully mapped to the current state of FreeGenes, with specific changes (and details for them) to make. So generally, everything that we discuss needs to translate to:

• how do we need to make changes to models for Parts and CompositeParts
• what is the "optimal" way to provide a new composite part, and then generate the "correct" list of parts to link to in FreeGenes?
• how do functions need to be modified (both client and server side) to support this?

I've implemented the basic working endpoint (detailed previously) to do this, so we need to start from that.

Good luck with lab meeting! I've been there... sometimes a cool idea to discuss, and a few working white board markers can do magic ✨

[Koeng101]

The vision is really great! But for now, let's not lose sight of the current scope - we are adding CompositeParts (in their simplest form), the idea being to build up to this vision.

Yep! That's why architectures aren't a thing yet, but I just wanted to justify why I didn't think composites needed to have sub-composites or anything like that without a cop-out.

how do we need to make changes to models for Parts and CompositeParts

Right now, I think I just need to start building CompositeParts to figure it what needs to be done. I think we should only start touching parts once CompositeParts are cozy in the database.

what is the "optimal" way to provide a new composite part, and then generate the "correct" list of parts to link to in FreeGenes?

The optimal way is to do a simulated GoldenGate run on a couple parts. Good thing, we literally just got the physical DNA to do this (so I can show what that looks like with real data in the database. I can also show what that looks like with real robots with mostly functioning code). Bad thing, we need for production-level import of plates from Twist's API to work. Basically, I think that has to be done later, after I've imported all the CompositeParts we have so far - since that's gonna take a while with a few issues coming up with part types.

I think your algorithm works great for annotating incoming sequences from Twist, with one exception (1). My favorite part is that once I establish a few more parts, importation from Twist is super easy with the code you've written so far.

how do functions need to be modified (both client and server side) to support this?

(1) The detection of parts has to work on a a circular string. If we are looking for "AAAA", we'd have to detect that on "GGAAAAGG" and "AAGGGGAA". This is because plasmids are physically circles.

Good luck with lab meeting! I've been there... sometimes a cool idea to discuss, and a few working white board markers can do magic

Thanks!

[shea256]

@Koeng101 wrote:

Why the difference? Simply put, there are many ways to instantiate a "A GFP Composite" - you could use a hundred different promoters, a hundred different RBSs, a hundred different terminators. All are different composite parts (since composite parts will be physically be different) but all are GFP Composites.

This is very cool and makes a lot of sense especially in an engineering context (modularity is valuable).

This also tells me that showing composite-composites is not actually useful or desired.

Therefore, it seems like we should prioritize finding the smallest possible parts rather than the largest possible parts.

@Koeng101 you mentioned that 20 character sequences are probably the smallest we'll need to match against, but I see that some of the most frequently used parts are actually 12-15 characters.

http://parts.igem.org/Frequently_Used_Parts

@vsoch wrote:

The vision is really great! But for now, let's not lose sight of the current scope - we are adding CompositeParts (in their simplest form), the idea being to build up to this vision. But we have to start simple - so all of the above is great, but it needs to be carefully mapped to the current state of FreeGenes, with specific changes (and details for them) to make.

Absolutely. I think what this translates to in the short term is that the smallest possible non-overlapping parts should be prioritized in the queue.

And we can maybe use very simple sequence clues like verifying that coding sequences are multiples of 3's and have start and stop codons.

Do y'all agree with this?

I could spend a bit of time thinking about how such an algorithm could be implemented if this is the case.

@Koeng101 Do you also think you could provide us with a handful or so of interesting test cases?

[vsoch]

(1) The detection of parts has to work on a a circular string. If we are looking for "AAAA", we'd have to detect that on "GGAAAAGG" and "AAGGGGAA". This is because plasmids are physically circles.

Oh that's actually really cool - and I almost asked you about circles (but then totally forgot). I think it's easy to do, I'll put in a PR in a few minutes.