Loading...
Searching...
No Matches
aligned_sequence_builder.hpp
Go to the documentation of this file.
// SPDX-FileCopyrightText: 2006-2025 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
#pragma once
#include <concepts>
#include <ranges>
#include <type_traits>
#include <vector>
#include <seqan3/alignment/aligned_sequence/aligned_sequence_concept.hpp>
#include <seqan3/alignment/decorator/gap_decorator.hpp>
#include <seqan3/alignment/matrix/detail/matrix_coordinate.hpp>
#include <seqan3/alignment/matrix/detail/trace_directions.hpp>
#include <seqan3/alphabet/gap/gapped.hpp>
#include <seqan3/core/detail/is_class_template_declarable.hpp>
#include <seqan3/utility/type_traits/concept.hpp>
#include <seqan3/utility/type_traits/lazy_conditional.hpp>
#include <seqan3/utility/views/convert.hpp>
#include <seqan3/utility/views/slice.hpp>
#include <seqan3/utility/views/type_reduce.hpp>
namespace seqan3::detail
{
template <std::ranges::viewable_range range_t>
struct make_aligned_sequence_type
{
private:
// The following expressions are used to check if the sequence types can be used as template arguments for the
// seqan3::gap_decorator. Ranges that do not model std::random_access_range for instance cannot be augmented with
// the gap_decorator and need to be copied instead.
using unaligned_sequence_type = decltype(std::declval<range_t>() | views::type_reduce | views::slice(0, 1));
public:
using type = lazy_conditional_t<is_class_template_declarable_with_v<gap_decorator, unaligned_sequence_type>,
lazy<gap_decorator, unaligned_sequence_type>,
lazy<std::vector, gapped<std::ranges::range_value_t<unaligned_sequence_type>>>>;
};
template <std::ranges::viewable_range first_sequence_t, std::ranges::viewable_range second_sequence_t>
struct make_pairwise_alignment_type
{
using first_aligned_t = typename make_aligned_sequence_type<first_sequence_t>::type;
using second_aligned_t = typename make_aligned_sequence_type<second_sequence_t>::type;
static_assert(seqan3::writable_aligned_sequence<first_aligned_t>,
"first_aligned_t is required to model seqan3::writable_aligned_sequence!");
static_assert(seqan3::writable_aligned_sequence<second_aligned_t>,
"second_aligned_t is required to model seqan3::writable_aligned_sequence!");
using type = std::tuple<first_aligned_t, second_aligned_t>;
};
template <std::ranges::viewable_range fst_sequence_t, std::ranges::viewable_range sec_sequence_t>
class aligned_sequence_builder
{
public:
using alignment_type = typename make_pairwise_alignment_type<fst_sequence_t, sec_sequence_t>::type;
struct [[nodiscard]] result_type
{
std::pair<size_t, size_t> first_sequence_slice_positions{};
std::pair<size_t, size_t> second_sequence_slice_positions{};
alignment_type alignment{};
};
constexpr aligned_sequence_builder()
requires std::default_initializable<type_reduce_t<fst_sequence_t>>
&& std::default_initializable<type_reduce_t<sec_sequence_t>>
= default;
constexpr aligned_sequence_builder(aligned_sequence_builder const &) = default;
constexpr aligned_sequence_builder(aligned_sequence_builder &&) = default;
constexpr aligned_sequence_builder & operator=(aligned_sequence_builder const &) = default;
constexpr aligned_sequence_builder & operator=(aligned_sequence_builder &&) = default;
~aligned_sequence_builder() = default;
constexpr aligned_sequence_builder(fst_sequence_t fst_rng, sec_sequence_t sec_rng) :
fst_rng{views::type_reduce(std::forward<fst_sequence_t>(fst_rng))},
sec_rng{views::type_reduce(std::forward<sec_sequence_t>(sec_rng))}
{}
template <std::ranges::input_range trace_path_t>
result_type operator()(trace_path_t && trace_path)
{
static_assert(std::same_as<std::ranges::range_value_t<trace_path_t>, trace_directions>,
"The value type of the trace path must be seqan3::detail::trace_directions");
result_type res{};
auto trace_it = std::ranges::begin(trace_path);
std::tie(res.first_sequence_slice_positions.second, res.second_sequence_slice_positions.second) =
std::pair<size_t, size_t>{trace_it.coordinate()};
std::vector<std::pair<trace_directions, size_t>> trace_segments;
while (trace_it != std::ranges::end(trace_path))
{
trace_directions last_dir = *trace_it;
size_t span = 0;
for (; trace_it != std::ranges::end(trace_path) && *trace_it == last_dir; ++trace_it, ++span)
{}
trace_segments.emplace_back(last_dir, span);
}
std::tie(res.first_sequence_slice_positions.first, res.second_sequence_slice_positions.first) =
std::pair<size_t, size_t>{trace_it.coordinate()};
assign_unaligned(
std::get<0>(res.alignment),
std::views::all(fst_rng)
| views::slice(res.first_sequence_slice_positions.first, res.first_sequence_slice_positions.second));
assign_unaligned(
std::get<1>(res.alignment),
std::views::all(sec_rng)
| views::slice(res.second_sequence_slice_positions.first, res.second_sequence_slice_positions.second));
// Now we need to insert the values.
fill_aligned_sequence(trace_segments | std::views::reverse,
std::get<0>(res.alignment),
std::get<1>(res.alignment));
return res;
}
private:
template <typename reverse_traces_t, typename fst_aligned_t, typename sec_aligned_t>
void fill_aligned_sequence(reverse_traces_t && rev_traces,
fst_aligned_t & fst_aligned,
sec_aligned_t & sec_aligned) const
{
if (std::ranges::empty(rev_traces))
return;
auto fst_it = std::ranges::begin(fst_aligned);
auto sec_it = std::ranges::begin(sec_aligned);
for (auto const & [dir, span] : rev_traces)
{
assert(dir == trace_directions::up || dir == trace_directions::left || dir == trace_directions::diagonal);
if (dir == trace_directions::up)
fst_it = insert_gap(fst_aligned, fst_it, span);
if (dir == trace_directions::left)
sec_it = insert_gap(sec_aligned, sec_it, span);
fst_it += span;
sec_it += span;
}
}
type_reduce_t<fst_sequence_t> fst_rng;
type_reduce_t<sec_sequence_t> sec_rng;
};
template <std::ranges::viewable_range fst_sequence_t, std::ranges::viewable_range sec_sequence_t>
aligned_sequence_builder(fst_sequence_t &&,
sec_sequence_t &&) -> aligned_sequence_builder<fst_sequence_t, sec_sequence_t>;
} // namespace seqan3::detail
aligned_sequence_concept.hpp
Includes the aligned_sequence and the related insert_gap and erase_gap functions to enable stl contai...
std::declval
T declval(T... args)
std::vector::emplace_back
T emplace_back(T... args)
std::forward
T forward(T... args)
gap_decorator.hpp
Provides seqan3::gap_decorator.
gapped.hpp
Provides seqan3::gapped.
seqan3::insert_gap
std::ranges::iterator_t< range_type > insert_gap(range_type &rng, std::ranges::iterator_t< range_type > const pos_it, typename range_type::size_type const size=1)
An implementation of seqan3::writable_aligned_sequence::insert_gap for ranges with the corresponding ...
Definition aligned_sequence_concept.hpp:409
seqan3::field::alignment
@ alignment
The (pairwise) alignment stored in an object that models seqan3::detail::pairwise_alignment.
Definition record.hpp:78
seqan3::views::slice
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition slice.hpp:137
seqan3::views::type_reduce
constexpr auto type_reduce
A view adaptor that behaves like std::views::all, but type erases certain ranges.
Definition type_reduce.hpp:147
is_class_template_declarable.hpp
Provides a type trait for verifying valid template declarations.
lazy_conditional.hpp
Provides lazy template instantiation traits.
matrix_coordinate.hpp
Provides seqan3::detail::matrix_index, seqan3::detail::matrix_coordinate and associated strong types.
seqan3::type_reduce_t
decltype(views::type_reduce(std::declval< t >())) type_reduce_t
Deduces the return value of seqan3::views::type_reduce.
Definition type_reduce.hpp:159
slice.hpp
Provides seqan3::views::slice.
std::tie
T tie(T... args)
trace_directions.hpp
Provides the declaration of seqan3::detail::trace_directions.
type_reduce.hpp
Provides seqan3::views::type_reduce.
type_traits
concept.hpp
Provides the concepts seqan3::transformation_trait and seqan3::unary_type_trait.
convert.hpp
Provides seqan3::views::convert.
vector
Hide me