aligned_sequence_builder.hpp

Go to the documentation of this file.

// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2024 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