SeqAn3  3.0.2
The Modern C++ library for sequence analysis.
Search

Data structures and algorithms for the search of query sequences in a large collection of text. More...

+ Collaboration diagram for Search:

Modules

 Configuration
 Data structures and utility functions for configuring search algorithm.
 
 DREAM Index
 Provides seqan3:interleaved_bloom_filter.
 
 FM Index
 Provides seqan3:fm_index and seqan3:bi_fm_index as well as respective cursors.
 
 k-mer Index
 Implementation of shapes for a k-mer Index.
 

Classes

class  seqan3::search_result< query_id_type, cursor_type, reference_id_type, reference_begin_position_type >
 The result class generated by the seqan3::seach algorithm. More...
 

Functions

template<fm_index_specialisation index_t, std::ranges::forward_range queries_t, typename configuration_t = decltype(search_cfg::default_configuration)>
auto seqan3::search (queries_t &&queries, index_t const &index, configuration_t const &cfg=search_cfg::default_configuration)
 Search a query or a range of queries in an index. More...
 

Detailed Description

Data structures and algorithms for the search of query sequences in a large collection of text.

Introduction

Searching is a key component in many sequence analysis tools. The search module is a powerful and easy way to search sequences in a large text or an arbitrary nested collection of texts. When it comes to searching, indices are a core component for searching large amounts of data and are used for tools such as read mappers, assemblers or protein search tools.

SeqAn currently implements only the FM index and a k-mer index is planned. The FM index works with arbitrary pattern lengths and error numbers.

Search algorithm

The Search module offers a simple unified interface for searching a query in a large indexed text. The algorithm chooses the best search method based on the provided index.

FM index

The search algorithms for FM indices implement either a trivial backtracking approach or an optimum search scheme. The latter are currently only available for searches with up to three errors using bidirectional indices. In the future we plan to improve the optimum search schemes to handle higher error counts.

Reference:

Kianfar, K., Pockrandt, C., Torkamandi, B., Luo, H., & Reinert, K. (2018).

Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index. bioRxiv, 301085. https://doi.org/10.1101/301085

K-mer index

A k-mer index can be used to efficiently retrieve all occurrences of a certain k-mer in the text. The k-mer can be either an exact string of length k or it can contain one or more wildcards, which denote positions of arbitrary characters.

An exact k-mer is represented as seqan3::ungapped, and wildcards can be defined with seqan3::shape. Please check the respective documentation for details and examples.

Note
The k-mer index is not yet implemented.
See also
seqan3::views::kmer_hash
seqan3::views::minimiser

Function Documentation

◆ search()

template<fm_index_specialisation index_t, std::ranges::forward_range queries_t, typename configuration_t = decltype(search_cfg::default_configuration)>
auto seqan3::search ( queries_t &&  queries,
index_t const &  index,
configuration_t const &  cfg = search_cfg::default_configuration 
)
inline

Search a query or a range of queries in an index.

Template Parameters
index_tMust model seqan3::fm_index_specialisation.
queries_tMust model std::ranges::random_access_range over the index's alphabet and std::ranges::sized_range. A range of queries must additionally model std::ranges::forward_range and std::ranges::sized_range.
Parameters
[in]queriesA single query or a range of queries.
[in]indexString index to be searched.
[in]cfgA configuration object specifying the search parameters (e.g. number of errors, error types, output format, etc.).
Returns
A seqan3::algorithm_result_generator_range with value type of seqan3::search_result.

Header File

#include <seqan3/search/search.hpp>

Complexity

Each query with $e$ errors takes $O(|query|^e)$ where $e$ is the maximum number of errors.

Exceptions

Strong exception guarantee if iterating the query does not change its state and if invoking a possible delegate specified in cfg also has a strong exception guarantee; basic exception guarantee otherwise.

Example

#include <vector>
int main()
{
using seqan3::operator""_dna4;
std::vector<seqan3::dna4_vector> genomes{"CGCTGTCTGAAGGATGAGTGTCAGCCAGTGTA"_dna4,
"ACCCGATGAGCTACCCAGTAGTCGAACTG"_dna4,
"GGCCAGACAACCCGGCGCTAATGCACTCA"_dna4};
std::vector<seqan3::dna4_vector> queries{"GCT"_dna4, "ACCC"_dna4};
// build an FM index
seqan3::fm_index index{genomes};
// search for the queries "GCT" and "ACCC"
for (auto && result : seqan3::search(queries, index))
seqan3::debug_stream << result << '\n';
// This should result in:
// <query_id:0, reference_id:0, reference_pos:1>
// <query_id:0, reference_id:1, reference_pos:9>
// <query_id:0, reference_id:2, reference_pos:16>
// <query_id:1, reference_id:1, reference_pos:0>
// <query_id:1, reference_id:1, reference_pos:12>
// <query_id:1, reference_id:2, reference_pos:9>
}
debug_stream.hpp
Provides seqan3::debug_stream and related types.
dna4.hpp
Provides seqan3::dna4, container aliases and string literals.
all.hpp
Meta-header for the FM index module.
seqan3::fm_index
The SeqAn FM Index.
Definition: fm_index.hpp:194
vector
search.hpp
Provides the public interface for search algorithms.
seqan3::debug_stream
debug_stream_type debug_stream
A global instance of seqan3::debug_stream_type.
Definition: debug_stream.hpp:42
seqan3::search
auto search(queries_t &&queries, index_t const &index, configuration_t const &cfg=search_cfg::default_configuration)
Search a query or a range of queries in an index.
Definition: search.hpp:105