Everybody is welcome to officially join the team. This does not involve any duties. Just contribute features you need for your own work. To join, please post here.

Dear @rust-bio/contributors, @MikkelSchubert, @mbrubeck, @veldsla, @bpr, @rednum, @natir, @flying-sheep, @althonos, @llogiq, @eclarke, @skade, @parir, @marcsch, @bow, @apirogov, @mahdi-b, @audy, @mariokostelac, @zitsen, @ghost,

I am currently writing a grant application for the sustainable development of Rust-Bio. For this, it is beneficial to name the research projects, tools or libraries, that use the software. Would you be so kind to post stuff you know about or work on yourself? If you don't mind, please also mention unpublished projects.

Thank you so much in advance! If we get the grant, we can hire a full-time developer.

Best, Johannes

Added an orf research algorithm.

Matched orf are returned as &[u8]. The algorithm only searches for orf in the 3 possible reading frames of the provided sequence without examining reverse complementary strand sequence. If it did, then it would be necessary to calculate the reverse complementary strand, and orf couldn't be returned as slices because the reverse complementary strand sequence wouldn't live outside of the function.

The complexity of this algorithm is linear, the 3 reading frames are read simultaneously which means the sequence only needs to be parsed one time.

Refining the method could include comparing the gc content of the obtained orf to the gc content of the whole sequence (which is why a gc.rs is present in the seq_analysis folder).

I ended up writing a blog post about the tools I used for profiling the change I proposed to Occ::get. Fun story, @aatch pointed out on Reddit that the slowdown in some other versions I had tried was probably due to the overhead of dealing with alignment in a vectorized version of the function, and noted that 3 may be an odd sample rate to test with the FMIndex. As an example, bowtie2's FM index appears to default to a sampling rate of 32, and I've seen a few cases of using higher rates as well.

The version of Occ::get proposed by Aatch is at approximate parity with the filter/count version for performance at a sampling rate of 32 (just a tiny bit slower), but it quickly gets much, much faster as the sampling rate increases. For example, with a sampling rate of 128 (in use in one of my applications):

filter/count, k = 128

test search_index_seeds ... bench:     179,442 ns/iter (+/- 1,947)

vectorized, k = 128

test search_index_seeds ... bench:     152,368 ns/iter (+/- 433)

filter/count, k = 64

test search_index_seeds ... bench:     105,141 ns/iter (+/- 1,665)

vectorized, k = 64

test search_index_seeds ... bench:      99,044 ns/iter (+/- 252)

filter/count, k = 32

test search_index_seeds ... bench:      74,427 ns/iter (+/- 5,166)

vectorized, k = 32

test search_index_seeds ... bench:      75,333 ns/iter (+/- 303)

Seems like an overall win to me. At a k of 32, the averages are just slightly higher than the filter/count version, but well within the error margin reported by libtest.

The one downside here is that at smaller sampling rates, a non-vectorized version wins out:

filter/count, k = 8

test search_index_seeds ... bench:      40,598 ns/iter (+/- 1,170)

vectorized, k = 8

test search_index_seeds ... bench:      53,842 ns/iter (+/- 224)

Thoughts here? Without integer generics (at all) and specialization (in stable), I'm not sure it's possible to cleanly maximize performance of small sampling rates and large ones. I'm biased here because I'm working with very large indices that need high sampling rates, but I'm not sure what other values of k are "in the wild."

In making SampledSuffixArray work, I discovered that multiple "canonical" implementations of FMIndex don't seem to support multiple sentinels in the text. Ben Langmead's Python notebooks host an implementation which can't handle multiple sentinels, and it looks like SeqAn doesn't either (although they do in a roundabout way by using a generalized suffix array).

So the question I have is -- is it possible to support a sampled suffix array in rust-bio without breaking the FMDIndex? I see some potential options:

• Make it clear in docs (and in code, somehow?) that only text with a single sentinel can be used in a SampledSuffixArray. Prevent FMDIndex-produced intervals from querying a SampledSuffixArray, etc.
• Implement a generalized suffix array and sidestep the problem (although I'm not sure what interaction that has with sampling, and have only glanced at the literature on them)
• Find a way to make a single-sequence suffix array sampleable without breaking on multiple sentinels. I haven't seen any research yet on this exact issue, in part because I think most who need to support multiple sequences are building generalized SAs.

I'm not sure what the best course of action is, but I'm eager to push forward on sampled SAs, so I'm very curious what others thoughts are here.

I'd like to create a tracking-issue for the branch I'm working on to add a partial-order aligner to the repetoire of alignment tools in rust-bio: https://github.com/rust-bio/rust-bio/tree/partial-order-aligner

To make the code reach a sort of minimum viable product-level, it still needs:

• Convert main() and example4.fa to inline example code
• Add unit-tests
• Individual read-path tracking and multi-alignment sequence output
• Make the internal aligner a member variable and make it customizabie at instantiation
• Some form of user-specified path-pruning

Beyond that, I am open to suggestions, particularly if some of the more experienced contributors have suggestions for improving the API, or stylistic or efficiency improvements to suggest for the code itself.

@cramertj reminded me of this with a comment on a PR. A number of data structures are implemented as type aliases currently:

• https://github.com/rust-bio/rust-bio/blob/master/src/data_structures/suffix_array.rs#L26
• https://github.com/rust-bio/rust-bio/blob/master/src/data_structures/bwt.rs#L17
• https://github.com/rust-bio/rust-bio/blob/master/src/stats/mod.rs#L14
• https://github.com/rust-bio/rust-bio/blob/master/src/alphabets/mod.rs#L27
• https://github.com/rust-bio/rust-bio/blob/master/src/pattern_matching/kmp.rs#L31

However, I think that using tuple structs/newtypes (pub struct RawSuffixArray(Vec<usize>)) would grant some extra compile-time verification to the use of these data structures (i.e. to prevent accidentally giving any old Vec to a function which needs RawSuffixArray), along with better error messages.

This would be a significant change to the API, but would only break clients who used the underlying types in a function signature, rather than the aliases. It would also allow greater leeway in the future to change the representation of the data structures without it being a breaking change.

Thoughts?

Updates for examples to FASTA (#295) and GFF (#297) file reading and writing. I've updates FASTA and BED examples to be consistent.

Please excuse errors as I'm new at Rust. I hope this helps. Suggestions to improve it before merging are welcome!

If there is recommended (quick) way to test whether these examples work, that would be helpful. I have files of these format(s) that I can test it on in a Linux environment.

The package builds locally but I think examples are commented out so of course it does.

Add a function for hamming distance hamm_dist + doc + test + bench. Add a function for edit distance lev_dist + doc + test + bench. Add the pretty() method to Alignment to return a String with pretty formatted alignments + doc. Add 3x3 easy-to-use functions for computing alignments, scores and returning pretty formatted alignments + doc + test + bench for all of them.

Due to a bug in the global alignment method the benchmark bench_fn_global_score fails now.

Adds a method to bio::io::fasta::Reader that takes a path to a gunzip-compressed FASTA file and a single test to ensure each Record is identical between plain-text and compressed inputs. Adds flate2 as a library dependency.

A flate2::read::GzDecoder object can already be passed to Reader::new() on the user side, but I noticed there are no library methods for this functionality (I hope I didn't miss them) and figured this could be a good first-time contribution for a rust novice if there is interest. Implementation as a trait would probably be best for introducing this functionality library-wide. Happy to take that on if this sounds like a good idea to folks.

During the rust-bio docathon 2020 I created a logo for our discord channel. I finally found some time to prepare two additional versions and put on some finishing touches. If we would like to adopt a project logo, I would offer these as a suggestion (or an initial draft to iterate upon).

All of these are based on Ferris the Rustacean designed and released under CC0 1.0 by Karen Rustad Tölva. SVG versions, some background information on how these were created and png exports can be found at https://github.com/HenningTimm/rust-bio-logo.

Version 1: As used on the discord server

Version 2: As used on the discord server but with thicker lines

Version 3: With a curled strand

:robot: I have created a release *beep* *boop*

1.1.1 (2023-01-02)

Performance Improvements

• mark complement as inline (#510) (bd08234)

This PR was generated with Release Please. See documentation.

A common convention is to wrap lines at 60 characters in a FASTA file. Would it be possible to add an option to wrap the sequences when writing out to a file? For example:

/// Write a Fasta record with given id, optional description and sequence.
    pub fn write(&mut self, id: &str, desc: Option<&str>, seq: TextSlice<'_>) -> io::Result<()> {
        self.writer.write_all(b">")?;
        self.writer.write_all(id.as_bytes())?;
        if let Some(desc) = desc {
            self.writer.write_all(b" ")?;
            self.writer.write_all(desc.as_bytes())?;
        }
        self.writer.write_all(b"\n")?;
        for chunk in seq.chunks(wrap) {
            self.writer.write_all(chunk)?;
            self.writer.write_all(b"\n")?;
        }
        self.writer.write_all(b"\n")?;

        Ok(())
    }

This is still a WIP, I've tried to understand the function and what it does and document it to the best of my abilities. To answer the original post:

• allowed_mismatches is strictly tested >therefore there's indeed a maximum of allowed_mismatches + 1 mismatch possible.
• Output matches don't seem to undergo any kind of overlapping verification, therefore no need to know incase of overlaping mismatches close #494

I spent a good hour debugging backward_search using the code fragment from backward_search: https://github.com/rust-bio/rust-bio/blob/eb9d378c70bc43d1dcf477e48cb167802799a546/src/data_structures/fmindex.rs#L103-L145

Turns out, the reference fasta I read in didn't have a sentinel character $ at the end. Lacking this terminal $ makes backward_search produce wrong results.

While the example texts do contain that character (that's how I got the idea to attach it to my reference) - it's not mentioned anywhere as far as I can see.

There should either be a note, or maybe even a check during creation of the FM index - unless there's a use case without terminal $. Or even more convenient - add a terminal $.

The following public function lacks a doc string: https://github.com/rust-bio/rust-bio/blob/43d198e87c69867fad39f07374d3fdcd9d879729/src/alignment/sparse.rs#L398

Some important questions to answer:

• exact meaning of allowed_mismatches, if I read the code correctly, extension happens independently on either side of the k-mer match, and stops after allowed_mismatches in each direction. So if you specify allowed_mismatches = 1 the extended match will actually contain 2 mismatches, one on either side - which is not what one may expect at all.
• whether output matches can overlap or not, if they don't overlap, will adjoining matches be merged or just border directly side-by-side?