The acgtrie from johnlonginotto

Example warp table in OUTPUT

Hello, I think your algorithm is very interesting and I'm trying to understand how it works. In the OUTPUT file, you give an example table of warp pipes for the string 'ACGACCC':

                                      row  A   C   T   G COUNT SEQ                                           
                                     ----------------------------------                                         
                                       0   1   2   0   3   7                                                   
                                       1   0   5   0   4   2   C                                             
                                       2   0   7   0   6   4                                                   
                                       3   0   0   0   0   1   ACCC                                          
                                       4   0   0   0   0   1   ACCC                                          
                                       5   0   0   0   0   1   C                                             
                                       6   0   0   0   0   1   ACCC                                          
                                       7   0   8   0   0   2                                                 
                                       8   0   0   0   0   1

But unless I don't understand this correctly, I think there is an error. The above table seems to indicate the presence of a AG 2-mer (with SEQ ACCC) via the path of rows 0 -> 1 -> 4.

I think this was supposed to be a GA 2-mer, encoded in the table as follows:

                                      row  A   C   T   G COUNT SEQ                                           
                                     ----------------------------------                                         
                                       0   1   2   0   3   7                                                   
                                       1   0   5   0   0   2   C                                             
                                       2   0   7   0   6   4                                                   
                                       3   4   0   0   0   1   ACCC                                          
                                       4   0   0   0   0   1   CCC                                          
                                       5   0   0   0   0   1   C                                             
                                       6   0   0   0   0   1   ACCC                                          
                                       7   0   8   0   0   2                                                 
                                       8   0   0   0   0   1

With the path 0 -> 3 -> 4 and SEQ CCC.

On top of that, I am wondering if the table should also have a warp pipe in row 4, column C, so as to store counts for GAC?

Or since SEQ contains CCC, can we assume that GAC, GACC, GACCC will all return a count of 1? In which case row 4 would be unnecessary, as this information would be contained in row 3.

Is the k-mer ACG account for in this table?

Thanks!

Order of characters in Up2bit

"Why use A-00, C-01, T-10, G-11? It's not in alphabetical order […] !!?‽"

Plus, it is confusing for humans.

Secondly, it's because there's a neat trick you can do to convert those four letters of ASCII directly into up2bit values. […] In some programming languages like C, we can cut out just those numbers very quickly.

I very much like your trick. 👍 To fix the order, another hack can be used.

    char n; // the nucleotide
    n &= 6; // mask
    n >>= 1; // shift
    n ^= (n >> 1); // fix lower bit

The lower bit is flipped only when the upper bit is 1 (i.e. G and T). In C this compiles down to five instructions, all bit-twiddling, making this method the fastest order-preserving "hash". (See also http://blog.kloetzl.info/hashing-nucleotides-to-two-bits/)

johnlonginotto / acgtrie Goto Github PK

acgtrie's People

Contributors

Stargazers

Watchers

acgtrie's Issues

Example warp table in OUTPUT

Order of characters in Up2bit

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent