Linear performance across edit distnace?

[JokingHero]

Hey,

First of all, I would like to say this software is a cool idea.

I am trying to benchmark SWOffinder against my software and I get the same execution time across increasing edit distance. I supply the same edit distance from 0 to 4 across all the parameters in your program: maxE maxM maxMB maxB. If this is true then there is very unique and interesting property of the algorithm., but seems to make no sense to me when searching for example distance 0.

I wonder whether you think this is reasonable given how the algorithm works, or you think something else must be broken in how I benchmark?

Best, Kornel

[ofiryaish]

Hi Kornel,

I assume you are doing it right. The algorithm is comprised of two steps. The runtime of the first step, which is the modified Smith-Waterman algorithm, depends only on the genome and sgRNA lengths. Only the second step runtime depends on the edit distance and the different thresholds for mismatches and bulges.

For the practical edit distance and mismatch and bulge thresholds, the runtime of the second step is neglectable compared to the first step. Therefore, you should see almost constant runtime for small edit distances like the one you used.

I can see Figure 4B in our manuscript, where we show that the runtime of the second step is neglectable compared to the first step and function of the thresholds, and you are getting almost constant runtime for practical edit distances for CRISPR off-target sites.

I hope this answers your question. Feel free to let me know if you need more information.

[ofiryaish]

Hi Kornel, Can you please confirm that this answers your question so that I can close the issue?

[JokingHero]

Yes, thank you for your answer. It is indeed very interesting. I have couple other questions related to your latest manuscript, how can I get in touch with you?

[ofiryaish]

Thank you.

You can send me an email to yaishof@post.bgu.ac.il