Non linear computation time w.r.t sequence Length

[waltergallegog]

Hello,
I've run some tests using some sub sequences of varying length. I have noticed the computation time I'm obtaining is not linear:

length	time [M:S]
30	0:0.010
300	0:0.271
1000	0:2.594
2000	2:5.201
3000	51:0.105
30000	22 hours and running

I'm using ipknot with the default model, which should use LinearPartition-C. From what I have seen in the paper, with this model, the computation time should follow a linear trend.
I'm missing something?

I have build ipknot as specified in the README.
In the paper I see that the experiments were performed using CPLEX. In my system I had GLPK and CPLEX installed but I suppose that with the default make command, GLPK is used. Could this explain the difference in the observed run times?

As input I'm using the NC_045512.2_Wuhan_seafood_market_pneumonia_virus_isolate_Wuhan-Hu-1__complete_genome sequence of almost 30000 bases. As running ipknot with this sequence has not finished after 22 hours, I started to test with increasingly long subsequences. Attached the .fasta and .db files together with the ipknot commands and outputs in case they can be useful.
ipknot-tests.tar.gz

Thanks for your support.

[waltergallegog]

I've compiled again ipknot with the ENABLE_CPLEX var and the computation time has been drastically reduced:

length	time[M:S]
2000	0:3.475
3000	0:5.453

is the linear behavior is only applicable when using CPLEX?
What about Gurobi?

[waltergallegog]

I've also compiled using gurubi and obtained slightly higher computational time values to those with CPLEX.

length	time[M::S]
2000	0:3.905
3000	0:6.362

By the way, I had to make some modifications to the cmake files in order to be able to compile (diff file attached gurubi-diff.txt):

• Add gurobi95 to the list of gurobi libs
• Fix typo GUROBI_INCLUDE_DIRS to GUROBI_INCLUDE_DIR
• Change the linking order from ${GUROBI_LIBRARY} ${GUROBI_CXX_LIBRARY} to ${GUROBI_CXX_LIBRARY} ${GUROBI_LIBRARY}

Additionally in the installation path /opt/gurobi951/linux64/lib I had to change the linking of the c++ lib.
From libgurobi_c++.a -> libgurobi_g++4.8.a to libgurobi_c++.a -> libgurobi_g++5.2.a.

I got part of the solution from: https://groups.google.com/g/gurobi/c/2yCgnRzkElE