-
Notifications
You must be signed in to change notification settings - Fork 82
Module: Alignments
alignment/detail/... // The core implementation of the alignment code, which is not prevent.
alignment/representation.hpp // Required only if output format is not score only.
alignment/representation/... // Data structures and utility functions to represent and work with alignments.
alignment/pairwise.hpp
alignment/pairwise/... // Defining the public API for calling the standard alignment algorithms.
alignment/msa.hpp
alignment/msa/... // Defining the public API for calling the msa algorithms.
alignment/seed_extend.hpp
alignment/seed_extend/...
alignment/split.hpp
alignment/split/...
alignment/banded_chain.hpp
alignment/banded_chain/...
In SeqAn 2.x we have several possibilities to represent an alignment.
In the following we introduce a new concept called aligned_sequence to replace the gaps data structures.
We will use then an alignment object to replace the Align-object which had many shortcomings.
template <typename t>
concept bool aligned_sequence_concept(t g)
{
requires sequence_concept<t>;
typename t::source_type;
// Element access
{ g[] const; } -> typename t::value_type;
// Manipulation
{ g.insert_gap(0, 4) } -> bool;
{ g.insert_gap(0, 4, hint) } -> bool;
{ g.remove_gap(0, 2) } -> bool;
{ g.remove_gap(0, 2, hint) } -> bool;
{ g.map_to_aligned_position(0) } -> typename t::size_type;
{ g.map_to_source_position(0) } -> typename t::size_type;
};Open questions:
- although it implements the view concept, it is not a lightweight object, maybe an action_concept<>???
from the range-proposal:
By specifying that Ranges do not own their elements, and further specifying that range adaptors operate on and produce Ranges (not Containers), we are able to answer these questions in a clear and consistent way. The result of a chain of range adaptors is always a lightweight object that is cheap to copy and assign (O(1) as opposed to O(N)), and that refers to elements whose lifetime is managed by some other object. Mutating an element through the resulting Range object mutates the underlying sequence. Copies of the resulting range are aliases to the same elements, and mutations to the elements are visible through all the aliased ranges.
- is the projection of the positions a find or map operation?
Array Gaps Uses simple interleaved blocks structure, where the first value gives the number of gaps and the second the number of sequence chars that follow. Requires linear scan of the block structure for random access.
template <typename underlying_t>
requires container_concept<underlying_t>
class aligned_sequence_linear_access
{
public:
protected:
private:
};Anchor Gaps Using sorted sequence anchors, which allow binary search for random access.
template <typename host_t>
class aligned_sequence_logarithmic_access
{
public:
protected:
private:
};Bitvector Gaps
- using rank-support query data structure to lookup a position in view space.
- sdsl::rank_support_v5? (+0.0625n bits)
- sdsl::rank_support_il? (+128 bits)
template <typename host_t>
class aligned_sequence_constant_access
{
public:
protected:
private:
};
template <typename first_t, typename ...remaining_ts>
requires aligned_sequence_concept<first_t> &&
(aligned_sequence_concept<remaining_ts> && ...)
class alignment : public std::vector<std::conditional_t<sizeof...(remaining_ts) == 0,
first_t,
std::variant<first_t, remaining_ts...>>
{
// TODO: Define the interface.
};What else do we want to do with the alignment view? Utility functions:
- merge two alignments.
- print/stream/serialize the alignment.
- compute statistics.
- ...
We will offer in general 4 public pairwise sequence alignment interfaces.
The 4 apis are split into, static configuration or dynamic configuration, and an align(...) and an align_and_then(...) interface.
The former is used to wait on the result, the latter can be used in asynchronous function calls, where a callback function is called at the end of the alignment.
We use a config object which must fulfil the align_config_static_concept. This defines a set of static constexpr parameters which are evaluated at compile time.
template <typename exec_policy_t, typename seq1_t, typename seq2_t,
typename align_config_t,
typename scoring_scheme_t>
requires is_execution_policy<exec_policy_t>::value &&
container_concept<seq1_t> &&
container_concept<seq2_t> &&
align_config_static_concept<align_config_static_t>
inline auto
align(exec_policy_t const & exec_policy,
seq1_t const & seq1,
seq2_t const & seq2,
align_config_t const & config,
align_parameters<scoring_scheme_t> const & params)
{
// delegate to corresponding functions.
// depending on configuration we can return several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
return {score, std::optional<output_format_t>{}};
}
// Continuation with callback function.
template <typename exec_policy_t, typename seq1_t, typename seq2_t,
typename align_config_t,
typename scoring_scheme_t,
typename callback_f>
requires is_execution_policy<exec_policy_t>::value &&
container_concept<seq1_t> &&
container_concept<seq2_t> &&
align_config_static_concept<align_config_t>
inline void
align_and_then(exec_policy_t const & exec_policy,
seq1_t const & seq1,
seq2_t const & seq2,
align_config_t const & config,
align_parameters<scoring_scheme_t> const & params)
callback_f && callback)
{
// delegate to corresponding functions.
// depending on configuration we can callback several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
// calls callback(score, std::optional<output_format_t>{});
}The runtime configuration creates a chain of continuators to create a static config object. The config type must fulfil the align_config_dynamic_concept. Since we cannot choose the output format at runtime to select a different return type, we cannot specify the output format in the dynamic config object.
template <typename exec_policy_t,
typename seq1_t,
typename seq2_t,
typename align_config_t,
typename scoring_scheme_t>
requires is_execution_policy<exec_policy_t>::value &&
container_concept<seq1_t> &&
container_concept<seq2_t> &&
align_config_dynamic_concept<align_config_t>
inline auto
align(exec_policy_t const & exec_policy, seq1_t const & seq1, seq2_t const & seq2,
align_config_t const & config,
align_parameters<scoring_scheme_t> const & params)
{
// delegate to corresponding functions.
// depending on configuration we can return several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
return {score, std::optional<aligned_sequence_view_constant_access>{}};
}
template <typename exec_policy_t, typename seq1_t, typename seq2_t,
typename align_config_t,
typename scoring_scheme_t,
typename callback_f>
requires is_execution_policy<exec_policy_t>::value &&
container_concept<seq1_t> &&
container_concept<seq2_t> &&
align_config_dynamic_concept<align_config_t>
inline void
align_and_then(exec_policy_t const & exec_policy,
seq1_t const & seq1,
seq2_t const & seq2,
align_config_t const & config,
align_parameters<scoring_scheme_t> const & params)
callback_f && callback)
{
// delegate to corresponding functions.
// depending on configuration we can callback several different things, like the alignment and score or just the score or the trace matrix or what ever we want.
// calls callback(score, std::optional<aligned_sequence_view_constant_access>{});
}https://gist.github.com/rrahn/aec7f42dfdb5c0dfc574b3a060628d9b