p-apsp

This code is an implementation of p-apsp [1], a new (parallel) algorithm based on [2] to solve the all-pairs suffix-prefix problem.

run

To run a test with K=100 strings from INPUT=dataset/c_elegans_ests_200.fasta, overlap threshold L=10, using T=4 threads type:

make p-apsp
make run DIR=dataset/ INPUT=c_elegans_ests_200.fasta K=100 L=10 OUTPUT=0 T=4

To run the sequential algorithm external/apsp_tustumi.cpp, type:

make apsp_tustumi
make run_tustumi DIR=dataset/ INPUT=c_elegans_ests_200.fasta K=100 L=10 OUTPUT=0

Output:

Both algorithms output .bin files at input folder (if OUTPUT=1).

In order to compare both output, change line 25 of main.cpp:

#define RESULT 1

to

#define RESULT 0

And type:

make
make run DIR=dataset/ INPUT=c_elegans_ests_200.fasta K=100 L=10 OUTPUT=1 T=4
make run_tustumi DIR=dataset/ INPUT=c_elegans_ests_200.fasta K=100 L=10 OUTPUT=1
make diff DIR=dataset/ INPUT=c_elegans_ests_200.fasta K=100

Note: all algorithms need sdsl-lite.

#references:

[1] Louza, F. A, Gog, S., Zanotto, L., Araujo, G., Telles, G. P. (2016). Parallel computation for the all-pairs suffix-prefix problem. In Proc SPIRE, pp 122-132, 2016, SpringerLink.

[2] Tustumi, W. H. A., Gog, S., Telles, G. P., Louza, F.A. (2016). An improved algorithm for the all-pairs suffix-prefix problem. Journal of Discrete Algorithms, 47, 34-43, Elsevier.