Poly store is a method to store DNA and search DNA sequences. Unlike many other methods for storing and indexing DNA sequences, Poly store is meant to be able to store everything - all DNA humanity has sequenced. The first implementation of Poly store was experimented with in #15
This is a difficult problem, but generally digests to a couple different necessary features:
- Must be disk based (Best method still up-in-the-air)
- Must be able to update index over time (SAIS algorithm will likely work best for this [1] )
- Must implement logarithmic-time search of DNA sequences (Suffix arrays are cool)
In order to implement Poly store, I think we should use a suffix-array data structure. This argument was made in #15 , and I think it still holds. The basic idea is we would have sequence
, suffix array
, lcp
(longest common prefix), and the seqhash position
arrays. sequence
would a massive DNA sequence compromising of all appended sequences together. suffix array
is the suffix array of sequence
, and lcp
is the lcp of that suffix array. seqhash position
is a list of sequence
positions that compose a seqhash, which references an object in a known database. Seqhashes are the universal identifiers we actually want in the end.
There will be a few necessary operations:
- Search sequence
- Search longest common substrings (for insert-time deduplication)
- Search longest common seqhash overlaps (for occasional storage deduplication)
- Sequence walking
Search Sequence
On a most basic level, searching sequence is done by doing a binary search on a suffix array. This operation is rather simple, and the data structure doesn't matter too much, so long as we can easily get the length of the suffix array and ensure that the suffix array is correctly sorted.
Search longest common substrings
For deduplication of new DNA getting inserted, it is important to be able to find the longest common substrings. So long as you can reversibly insert the new DNA sequence into the suffix array, this operation comes down to checking the local LCPs around the inserted DNA sequence, similar to the optimal deduplicator described in #15 under the initial post. As an added bonus, this step will also deduplicate the sequence against itself for repeated regions.
This can also be used to build relationship maps between species.
Search longest common seqhash overlaps
While the above algorithm for finding longest common substrings works well, it is insert-order dependent, where certain insert orders will be more efficient than others. This is concerning, and would require a smart insertion order. This, however, is quite solvable with some clever use of seqhash positions. There needs to be a way to calculate the most inefficient seqhash positions to occasionally rearrange the sequence. This is a little unclear, so here is an example:
Say the reference human genome has a section of sequence that looks like ... ATG GGG TAA ...
, however, it turns out most human beings have the sequence ... ATG GGA TAA ...
. If the reference human genome was inserted first, it will always split up the subsequent human sequences into two different positions. When you factor in the increased referencing costs, it makes sense to store the ... ATG GGA TAA ...
sequence and instead split the reference human genome.
Sequence walking
To do an alignment, you need a small sequence to get started with the approximately right positions. This sequence I call the "sequence seed", and is well illustrated in the Centrifuge paper [0]. After you get the proper locations of the seed, you walk down the sequence in both directions. If any seqhash position gets split while walking, you must branch to test the different possibilities.
This sequence walking can be enhanced by searching the longest common substrings (which reduces or eliminates the need for backtracking), so long as the lcp
array values are easy to search on.
Focus points
With these features and operations in mind, there are a few focus points that the end product will have to be good at:
- Efficient reversible transactions
- Efficient indexing and relationship referencing
- Fast insertion
Efficient transactions are necessary for implementing the continuous updating feature from the SAIS algorithm [0], and reversible transactions are necessary for searching longest common substrings.
Efficient indexing and relationship referencing are necessary for quickly moving through the relationships between seqhash positions
, suffix array
and sequence
lists. This especially is necessary for sequence walking, which needs to coordinate between the sequence
and seqhash positions
list often.
SQLite caps out at ~100K inserts per second in my testing - without very aggressive deduplication, it would take far too long to insert all DNA materials. This can be a problem, but it is unknown how big of a problem it will be with deduplication.
===
@TimothyStiles Thoughts? I'm thinking the biggest change here from last is the longest common substrings
problem, which turns out to be essential for a lot of interesting capacities, such as effective deduplication, phylogenetic / relationship tree building, and in-depth alignment.
References
[0] https://dx.doi.org/10.1101%2Fgr.210641.116
[1] https://zork.net/~st/jottings/sais.html