FMD-index

[sriram98v]

Hey @feldroop,

This is a fantastic crate. The Cursor API is awesome and I use it extensively. I would love to see the FMD-index implemented soon, as I would like a way to efficiently find MEMs between a pattern and a set of texts in an FMD-index.

As per my understanding of Heng Li's paper, we can construct an FMD-index for a collection of strings $T=R_0R_1...R_{n-1}$ by simply constructing an FM-index for the string $T=R_0\overline{R_0}R_1\overline{R_1}...R_{n-1}\overline{R_{n-1}}$, where $\overline{R_i}$ is the reverse complement of $R_i$. If my understanding is correct, the forward-backward algorithm would be the next step to implementing a MEM finder using an FMD-index, which can be done by using your Cursor API.

Is my understanding correct?

[feldroop]

(Note: I edited this message a lot)

Hi @sriram98v,

That's awesome to hear, thank you for the kind words! I think MEMs and the FMD-Index are the most natural next feature extension to the library, so I'll give them top priority. I will try to work on it, but I recently started a new job, so it might take some time.

I will have to make a large breaking change to the library and introduce traits that represent different search capabilities and are implemented by multiple FM-Index variants. This will probably also entail a complete refactor of the config API and other parts of the library. Initially, I thought I might get away without this, but now it seems like the FMD-Index search is different than the normal FM-Index search, and more similar to the search of the bidirectional FM-Index. This large refactor needed to be done at some point anyway, so it will be good to have the changes when I want to add more FM-Index variants in the future.

Regarding the FMD-Index, I will read up further on the algorithm, I don't know it in detail yet. For now, here are some things I'll probably have to do:

• add reverse complement functionality to alphabets
• add traits that represent different searches/cursors and implement them for the FM-Index
• add prelude to import the necessary traits
• implement construction on transformed text for FMD-Index (TODO: is it strictly necessary to use the reverse complement?)
• refactor config API with option for other FM-Index variants (with typestate to avoid misuse). For now, only FMD-Index
• implement forward/backward extension and search
• implement MEM search algorithm (or sMEM, I'm not sure what the difference is yet)
• add documentation and examples for all of the new features
• cite or at least link paper in README and docs
• future TODO think about whether a look-up table is worthwhile for the FMD-Index
• future TODO: think about whether MEM search can benefit from the batched optimization

Please let me know if I missed something. Is there a serious time contraint for you to get the FMD-Index feature?

[sriram98v]

I would ideally love for the FMD-index to be available By January, but this is not a serious time constraint. I would also like to contribute to this as it would be a valuable learning experience for me as well. I had originally started putting together traits and such for alphabets and included them below(maybe they would be of use to you!).

use core::fmt::{Debug, Display};
use core::fmt;

pub trait Alphabet: PartialOrd + Display + Debug + Hash + Eq + Default + Clone
{
    /// Checks if self is a terminal character
    fn is_terminal(&self)->bool;

    /// Returns a terminal character
    fn terminal()->Self;
}

#[derive(Debug, Default, Hash, Eq, PartialEq, Clone, Copy, PartialOrd)]
#[repr(u8)]
pub enum DNA{
    A = 2,
    C = 3,
    G = 4,
    T = 5,
    Terminal = 1,
   #[default] 
    End = 0,
}

impl Display for DNA{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self{
            DNA::A => write!(f, "{}", b'A'),
            DNA::C => write!(f, "{}", b'C'),
            DNA::G => write!(f, "{}", b'G'),
            DNA::T => write!(f, "{}", b'T'),
            _ => write!(f, ""),
        }
    }
}


impl Alphabet for DNA{
    fn is_terminal(&self)->bool {
        self==&DNA::Terminal
    }

    fn terminal()->Self {
        DNA::Terminal
    }
}

As for the checklist items, FMD-indexes do require Watson-Crick complements for construction. In an FMD-index, the interval (called a bi-interval in Section 2.4) is a three-element array where the second elements corresponds to the complement of a text in the index.

[feldroop]

January sounds like a reasonable goal, that should be possible. Regarding contributing, that's also very nice! I think it will be difficult for the large refactoring, because it touches many parts of the library and I already have a clear vision of how it should be done.

But afterwards, you could definitely help with the algorithm implementations and optimizations. I will keep you updated.

Regarding the code snippet you sent, I want the Alphabet to keep being a struct. I also experimented with it as a trait, but I am now convinced that it is not the correct way to go. Having it as a trait would only make sense if the different alphabets had significantly different internal logic to implement the API the FM-Index needs.