Hisat2 indexing

Question

[kiran]

Hello everyone,

thanks for your time.

Regarding Hisat2 Genome based indexing:

I was trying to understand the indexing part in different aligners, i understood bowtie2 and bwa versions, built with (BWT, SA, FM index).

I tried a lot to understand the graph based indexing but couldn't reach to the level to understand the GFM index, i need some suggestions and help to understand how did they build the graph and what does it mean by "Prefix sort graph - doubling and pruning", how is this graph constructed. i understood how the LM mapping part after prefix sorted graph.

I'll be very thankful for your suggestions.

1. How to understand prefix sorted graph which is saying doubling and pruning.

best regards, Kiran.

[kiran]

Hi,

I just realized that it is build based on the Finite automata theory, which is actually accepting the multiple string alignments possible.

1. Reverse deterministic automaton and prefix sorting them.

thanks.