-resoverlap / -seqoverlap option is extremely slow for very large alignments

[Mvila035]

Hi,

I was trying to use the -resoverlap / -seqoverlap options to clean a very large alignment of closely related viral sequences (~200,000 sequences; ~5,000 nt). Trimal was unable to finish the task within 16 hours of runtime.

I took a (rapid) look at the calculateSpuriousVector function in the alignment.cpp, which computes the overlap for each position of each sequence. It seems to me that the problem comes from multiple nested loops in this function. Instead of using 3 nested loops, the number of nt/aa, gaps, and unidentified bases could be computed once for each column rather than recomputed for each site of each sequence.

I implemented this in Python (using Numpy + Numba), and it runs in approximately 5 minutes (I will attach the code once I further test it).

Maybe it's an improvement that could be considered for a future release?

Thanks.

[nicodr97]

Hi, which version are you using? I thought that maybe this was already improved in v2, althogh I have checked the code and it seems that the 3 nested loops are still there.

For sure it would be nice to have your code. I'll let this issue as pending to implement it as part of the release of v2.

Thanks!

[Mvila035]

I pulled and compiled from the main branch so it should be version 1.5.1. Here is my code:

clean_alignment.py

It is fast(er) but uses a lot of memory (my file was ~0.7G and used 36G of memory). It most likely comes from lines 89 to 100, where I save large lists that scale with the size of the alignment. Instead, you could compute the resoverlap and seqoverlap in the same function.

Cheers!