Timeline for Counting k-mers
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 5, 2015 at 19:32 | comment | added | user9206 | After discussing it with FUZxxl, it seems you can make the suffix array of chr2.fa in under 30 seconds using only 1.1GB of RAM. | |
| Feb 5, 2015 at 9:19 | comment | added | user9206 | Let us continue this discussion in chat. | |
| Feb 5, 2015 at 0:52 | comment | added | FUZxxl | @Lembik I actually only tried SA-IS and it took over two minutes, which is so much more than one minute that it didn't seem worth trying the others. | |
| Feb 4, 2015 at 21:41 | comment | added | user9206 | @FUZxxl Which of the existing suffix array implementations have you managed to try? I couldn't get some of them to run at all. | |
| Feb 4, 2015 at 13:46 | comment | added | FUZxxl | @Lembik That's weird. Maybe I made a mistake copying the code? | |
| Feb 4, 2015 at 13:40 | comment | added | user9206 | @FUZxxl That's interesting. I found algo2.iti.kit.edu/sanders/papers/KulSan06a.pdf and also code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks . | |
| Feb 4, 2015 at 11:43 | comment | added | FUZxxl | @Lembik The algorithm I tried (SA-IS, dubbed the fastest one for this purpose) still takes about two minutes to suffix-sort the entire array. I don't think it can be parallelized. | |
| Feb 4, 2015 at 10:16 | comment | added | FUZxxl | @Lembik Indeed. It's just takes me a while to implement. Let me try… | |
| Feb 4, 2015 at 10:08 | comment | added | user9206 | @FUZxxl You can compute the suffix array in linear time so this could be promising. Whether you can actually get it under 1 minute is an interesting question. Some papers online seem to say you can usefully use multi cores to speed up suffix array construction too. | |
| Feb 3, 2015 at 23:21 | comment | added | FUZxxl | @Lembik My “improved” approach was to sort an array of suffixes of the input file lexicographically. Then for all k the equal k-mers are adjacent. The problem is that sorting like that takes quite a while, around 8 minutes on my machine. I was too lazy to devise a better sorting scheme. The advantage is, that after you have created that sorted array, you can generate the answer for each k rather quickly. If you want, you can even generate the answer for all k at once. | |
| Feb 3, 2015 at 20:49 | comment | added | Keith Randall | @Lembik: Longest repeated substring can be done in linear time. But I don't think it is very helpful - there are really long repeated substrings in the sample input, thousands of symbols at least. | |
| Feb 3, 2015 at 19:23 | comment | added | user9206 | How long do you think it takes to find the longest length of any repeated substring? I was thinking you automatically know all the answers for any k longer than that. | |
| Feb 3, 2015 at 16:19 | comment | added | Keith Randall | @FUZxxl: fixed. | |
| Feb 3, 2015 at 16:19 | history | edited | Keith Randall | CC BY-SA 3.0 |
Fix output format
|
| Feb 3, 2015 at 11:32 | comment | added | FUZxxl | This is a cool solution otherwise. | |
| Feb 3, 2015 at 10:37 | comment | added | FUZxxl | Please obey the output format; do not k. | |
| Feb 3, 2015 at 6:11 | history | edited | Keith Randall | CC BY-SA 3.0 |
Add instructions to compile and run
|
| Feb 3, 2015 at 6:05 | history | answered | Keith Randall | CC BY-SA 3.0 |