Skip to content

sauloal/debruijnindex

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

27 Commits

.vscode

.vscode

 
 

.gitignore

.gitignore

 
 

README.md

README.md

 
 

deBruijnDecodable.js

deBruijnDecodable.js

 
 

deBruijnDisplay.js

deBruijnDisplay.js

 
 

deBruijnJs.py

deBruijnJs.py

 
 

deBruijnJsTest.py

deBruijnJsTest.py

 
 

deBruijnJsTools.py

deBruijnJsTools.py

 
 

deBruijnSequence.py

deBruijnSequence.py

 
 

debdec.py

debdec.py

 
 

debdec_create.py

debdec_create.py

 
 

debdec_run.py

debdec_run.py

 
 

index.html

index.html

 
 

logger.py

logger.py

 
 

prettify.js

prettify.js

 
 

test.fasta

test.fasta

 
 

Repository files navigation

debruijnindex

TLDR

Generate a deBruijn Sequence that facilitates an efficient decoding algorithm due to J. Tuliani theis, porting the implementation of jgeisler0303

Description

Generate a deBruijn Sequence that facilitates an efficient decoding algorithm due to J. Tuliani.

Ports the implementation of (jgeisler0303)[https://github.com/jgeisler0303/deBruijnDecode] to python.

Alternative

https://github.com/alexbowe/debdec

Timing

4_7
(16384)
real    12m18.553s
user    11m49.953s
sys     00m21.078s

real    00m00.581s
user    00m00.484s
sys     00m00.094s

4_9
real    1m43.954s
user    1m43.766s
sys     0m0.125s

4_11
real    476m56.538s 7.9h
user    476m02.203s
sys       0m04.109s

206 272 
4_13 2.148 h =     89.5 days
4_15           24.353  days =            66 years
4_17                                 18.148 years
4_19                              4.936.266 years
4_21                          1.342.664.496 years

Timing - no matrix

4_03
real    0m00.153s
user    0m00.063s
sys     0m00.109s

4_05
real    0m00.160s
user    0m00.078s
sys     0m00.078s

4_07
real    0m00.261s
user    0m00.188s
sys     0m00.063s

4_09
real    0m02.264s
user    0m02.063s
sys     0m00.172s

4_11
real    0m33.539s
user    0m31.609s
sys     0m01.891s

4_13
real    9m15.806s
user    8m38.453s
sys     0m33.422s

Timing - no matrix - calculation

3     5     7     9     11    13   15      17         19           21
                                                      10yr         2.158yr
                                           30d        3.749d       787.973d
                                   10h     728h       89.995h      18.911.369h
                              9.5m 600m    43.683m    5.399.725m   1.134.682.152m
0.15s 0.16s 0.26s 2.26s 33.5s 555s 36.048s 2.621.014s 323.983.540s 68.080.929.144s
      1.01  1.62  8.69  14.8  16.6 42.77   72.71      123.61       210.1
            1.63  5.33  1.7   1.12

Numbers

3
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45] (2)
 INFO    :    L             : (1)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :    dbsequence    : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0, 3, 3, 3, 0, 0 ... 2, 1, 1, 1, 2, 2, 0, 0, 3, 0, 1, 2, 3, 0, 2, 3, 2, 0, 2, 1] (64)

5
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765] (4)
 INFO    :    L             : (3)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 3, 0, 2, 1, 1, 2, 1, 2, 3, 0, 0, 0, 1, 0, 2, 0, 0, 3, 0, 1] (1024)

7
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285] (6)
 INFO    :    L             : (5)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 1, 3, 0, 1, 0, 0, 1, 0, 0, 2, 3, 0, 1, 2, 0, 2, 2, 2, 2, 1] (16384)

9
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285, 49149, 196605] (8)
 INFO    :    L             : (7)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :      L[ 5]       : [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 3, 3, 1, 2, 0, 1, 0, 1 ... 0, 1, 0, 0, 1, 1, 1, 2, 2, 2, 0, 3, 3, 0, 2, 2, 0, 2, 0, 2] (16383)
 INFO    :      L[ 6]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 3, 0, 2, 3, 0, 2, 0, 2, 1, 0, 3, 0, 0, 0, 1, 0, 3, 0, 3, 0] (65535)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 0, 1, 3, 0, 1, 3, 1, 3, 2, 1, 0, 1, 1, 1, 2, 1, 0, 1, 0, 1] (262144)

11
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285, 49149, 196605, 786429, 3145725] (10)
 INFO    :    L             : (9)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :      L[ 5]       : [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 3, 3, 1, 2, 0, 1, 0, 1 ... 0, 1, 0, 0, 1, 1, 1, 2, 2, 2, 0, 3, 3, 0, 2, 2, 0, 2, 0, 2] (16383)
 INFO    :      L[ 6]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 3, 0, 2, 3, 0, 2, 0, 2, 1, 0, 3, 0, 0, 0, 1, 0, 3, 0, 3, 0] (65535)
 INFO    :      L[ 7]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 2, 1, 0, 0 ... 0, 0, 1, 0, 0, 1, 0, 1, 0, 2, 3, 3, 0, 1, 2, 0, 1, 1, 2, 2] (262143)
 INFO    :      L[ 8]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 3, 0, 1, 3, 0, 0 ... 3, 0, 1, 3, 0, 1, 3, 0, 2, 3, 2, 2, 2, 3, 1, 0, 1, 3, 1, 0] (1048575)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 3, 0, 1, 3, 0, 0 ... 0, 1, 2, 0, 1, 2, 0, 1, 3, 0, 3, 3, 3, 0, 2, 1, 2, 0, 2, 1] (4194304)

13
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285, 49149, 196605, 786429, 3145725, 12582909, 50331645] (12)
 INFO    :    L             : (11)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :      L[ 5]       : [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 3, 3, 1, 2, 0, 1, 0, 1 ... 0, 1, 0, 0, 1, 1, 1, 2, 2, 2, 0, 3, 3, 0, 2, 2, 0, 2, 0, 2] (16383)
 INFO    :      L[ 6]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 3, 0, 2, 3, 0, 2, 0, 2, 1, 0, 3, 0, 0, 0, 1, 0, 3, 0, 3, 0] (65535)
 INFO    :      L[ 7]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 2, 1, 0, 0 ... 0, 0, 1, 0, 0, 1, 0, 1, 0, 2, 3, 3, 0, 1, 2, 0, 1, 1, 2, 2] (262143)
 INFO    :      L[ 8]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 3, 0, 1, 3, 0, 0 ... 3, 0, 1, 3, 0, 1, 3, 0, 2, 3, 2, 2, 2, 3, 1, 0, 1, 3, 1, 0] (1048575)
 INFO    :      L[ 9]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 1, 0, 0 ... 0, 0, 1, 3, 3, 0, 2, 2, 3, 2, 2, 1, 0, 3, 3, 1, 2, 0, 0, 2] (4194303)
 INFO    :      L[10]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 1, 1 ... 1, 2, 3, 1, 1, 1, 2, 1, 0, 0, 3, 2, 0, 1, 1, 1, 3, 2, 3, 0] (16777215)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 1, 1 ... 2, 3, 0, 2, 2, 2, 3, 2, 1, 1, 0, 3, 1, 2, 2, 2, 0, 3, 0, 1] (67108864)

About

Generate a deBruijn Sequence that facilitates an efficient decoding algorithm due to J. Tuliani thesis, porting the implementation of jgeisler0303

Resources

Readme
Activity

Stars

0 stars

Watchers

2 watching

Forks

0 forks
Report repository

Releases

3 tags

Packages

No packages published

Languages