Question about extend_right Method in seqan3::fm_index

[Dhruv-mak]

Hello everyone,

I am working on implementing a data compression algorithm and I am using the seqan3 library, specifically the fm_index. You can find my project here: GitHub - Dhruv-mak/rlz.

I have a question regarding the behavior of the extend_right method on an fm_index_cursor.

Code Example
Here's a simplified version of the code I am working with:

int main(int argc, char const** argv) {
    using namespace seqan3::literals;

    std::string seq = "ACGTACCGT"
    seqan3::fm_index index{seq};

    auto cursor = index.cursor();
    cursor.extend_right('C');
    cursor.extend_right('G');
    cursor.extend_right('T');
    // continue extending the cursor
}

Question
When using the extend_right method and providing one character at a time to search for a substring, does the extend_right method:

1. Perform the search for the newly formed string from scratch each time a new character is added?
2. Or Narrow down the existing search range incrementally, similar to the backward_search function shown in the SeqAn3 FM Index documentation?

I want to understand if the extend_right method optimizes the search by building upon the previous state or if it starts the search from the beginning each time.

Additional Context
The reason I am asking this is that I have come across another repository, GitHub - skuruppu/RLZ, which implements a similar compression algorithm but uses a suffix_array instead. I have noticed a significant difference in the running time between the two implementations, with my implementation using fm_index taking almost three times longer. I am trying to identify if the difference in running time is due to how the extend_right method operates.

Additional Information
I have reviewed the SeqAn3 documentation regarding fm_index and extend_right, but I am still unclear on this aspect.
Any clarification or guidance would be greatly appreciated.
Thank you for your help!

[rrahn]

Hi @Dhruv-mak,

the cursor object stores the state of the last extend_right request, meaning that it narrows down the interval over the SA each time the search is extended to the right with a new character and does not search the query text from the beginning.
The performance differences you observe can have multiple reasons and it is hard to tell what it would be in you particular case. However, we have faster FM-index implementations that are yet not integrated within the main seqan library. Please have a look at this library here: https://github.com/SGSSGene/fmindex-collection.