SeqAn3 3.4.0-rc.1
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
aligned_sequence_builder.hpp
Go to the documentation of this file.
1// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
2// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
3// SPDX-License-Identifier: BSD-3-Clause
4
10#pragma once
11
12#include <concepts>
13#include <ranges>
14#include <type_traits>
15#include <vector>
16
28
29namespace seqan3::detail
30{
31
49template <std::ranges::viewable_range range_t>
50struct make_aligned_sequence_type
51{
52private:
53 // The following expressions are used to check if the sequence types can be used as template arguments for the
54 // seqan3::gap_decorator. Ranges that do not model std::random_access_range for instance cannot be augmented with
55 // the gap_decorator and need to be copied instead.
56
58 using unaligned_sequence_type = decltype(std::declval<range_t>() | views::type_reduce | views::slice(0, 1));
59
60public:
62 using type = lazy_conditional_t<is_class_template_declarable_with_v<gap_decorator, unaligned_sequence_type>,
63 lazy<gap_decorator, unaligned_sequence_type>,
64 lazy<std::vector, gapped<std::ranges::range_value_t<unaligned_sequence_type>>>>;
65};
66
74template <std::ranges::viewable_range first_sequence_t, std::ranges::viewable_range second_sequence_t>
75struct make_pairwise_alignment_type
76{
78 using first_aligned_t = typename make_aligned_sequence_type<first_sequence_t>::type;
80 using second_aligned_t = typename make_aligned_sequence_type<second_sequence_t>::type;
81
83 "first_aligned_t is required to model seqan3::writable_aligned_sequence!");
85 "second_aligned_t is required to model seqan3::writable_aligned_sequence!");
86
89};
90
112template <std::ranges::viewable_range fst_sequence_t, std::ranges::viewable_range sec_sequence_t>
113class aligned_sequence_builder
114{
115public:
117 using alignment_type = typename make_pairwise_alignment_type<fst_sequence_t, sec_sequence_t>::type;
118
120 struct [[nodiscard]] result_type
121 {
123 std::pair<size_t, size_t> first_sequence_slice_positions{};
125 std::pair<size_t, size_t> second_sequence_slice_positions{};
128 alignment_type alignment{};
129 };
130
134 constexpr aligned_sequence_builder()
135 requires std::default_initializable<type_reduce_t<fst_sequence_t>>
136 && std::default_initializable<type_reduce_t<sec_sequence_t>>
137 = default;
138 constexpr aligned_sequence_builder(aligned_sequence_builder const &) = default;
139 constexpr aligned_sequence_builder(aligned_sequence_builder &&) = default;
140 constexpr aligned_sequence_builder & operator=(aligned_sequence_builder const &) = default;
141 constexpr aligned_sequence_builder & operator=(aligned_sequence_builder &&) = default;
142 ~aligned_sequence_builder() = default;
143
148 constexpr aligned_sequence_builder(fst_sequence_t fst_rng, sec_sequence_t sec_rng) :
149 fst_rng{views::type_reduce(std::forward<fst_sequence_t>(fst_rng))},
150 sec_rng{views::type_reduce(std::forward<sec_sequence_t>(sec_rng))}
151 {}
153
168 template <std::ranges::input_range trace_path_t>
169 result_type operator()(trace_path_t && trace_path)
170 {
171 static_assert(std::same_as<std::ranges::range_value_t<trace_path_t>, trace_directions>,
172 "The value type of the trace path must be seqan3::detail::trace_directions");
173
174 result_type res{};
175 auto trace_it = std::ranges::begin(trace_path);
176 std::tie(res.first_sequence_slice_positions.second, res.second_sequence_slice_positions.second) =
177 std::pair<size_t, size_t>{trace_it.coordinate()};
178
180
181 while (trace_it != std::ranges::end(trace_path))
182 {
183 trace_directions last_dir = *trace_it;
184 size_t span = 0;
185 for (; trace_it != std::ranges::end(trace_path) && *trace_it == last_dir; ++trace_it, ++span)
186 {}
187
188 trace_segments.emplace_back(last_dir, span);
189 }
190
191 std::tie(res.first_sequence_slice_positions.first, res.second_sequence_slice_positions.first) =
192 std::pair<size_t, size_t>{trace_it.coordinate()};
193
194 assign_unaligned(
195 std::get<0>(res.alignment),
196 std::views::all(fst_rng)
197 | views::slice(res.first_sequence_slice_positions.first, res.first_sequence_slice_positions.second));
198 assign_unaligned(
199 std::get<1>(res.alignment),
200 std::views::all(sec_rng)
201 | views::slice(res.second_sequence_slice_positions.first, res.second_sequence_slice_positions.second));
202
203 // Now we need to insert the values.
204 fill_aligned_sequence(trace_segments | std::views::reverse,
205 std::get<0>(res.alignment),
206 std::get<1>(res.alignment));
207
208 return res;
209 }
210
211private:
218 template <typename reverse_traces_t, typename fst_aligned_t, typename sec_aligned_t>
219 void fill_aligned_sequence(reverse_traces_t && rev_traces,
220 fst_aligned_t & fst_aligned,
221 sec_aligned_t & sec_aligned) const
222 {
223 if (std::ranges::empty(rev_traces))
224 return;
225
226 auto fst_it = std::ranges::begin(fst_aligned);
227 auto sec_it = std::ranges::begin(sec_aligned);
228
229 for (auto const & [dir, span] : rev_traces)
230 {
231 assert(dir == trace_directions::up || dir == trace_directions::left || dir == trace_directions::diagonal);
232
233 if (dir == trace_directions::up)
234 fst_it = insert_gap(fst_aligned, fst_it, span);
235
236 if (dir == trace_directions::left)
237 sec_it = insert_gap(sec_aligned, sec_it, span);
238
239 fst_it += span;
240 sec_it += span;
241 }
242 }
243
244 type_reduce_t<fst_sequence_t> fst_rng;
245 type_reduce_t<sec_sequence_t> sec_rng;
246};
247
253template <std::ranges::viewable_range fst_sequence_t, std::ranges::viewable_range sec_sequence_t>
254aligned_sequence_builder(fst_sequence_t &&,
255 sec_sequence_t &&) -> aligned_sequence_builder<fst_sequence_t, sec_sequence_t>;
257} // namespace seqan3::detail
Includes the aligned_sequence and the related insert_gap and erase_gap functions to enable stl contai...
T begin(T... args)
T emplace_back(T... args)
Provides seqan3::gap_decorator.
Provides seqan3::gapped.
@ alignment
The (pairwise) alignment stored in an object that models seqan3::detail::pairwise_alignment.
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition slice.hpp:175
The generic concept for an aligned sequence that is writable.
Provides a type trait for verifying valid template declarations.
Provides lazy template instantiation traits.
Provides seqan3::detail::matrix_index, seqan3::detail::matrix_coordinate and associated strong types.
SeqAn specific customisations in the standard namespace.
Provides seqan3::views::slice.
T tie(T... args)
Provides the declaration of seqan3::detail::trace_directions.
Provides seqan3::views::type_reduce.
Provides the concepts seqan3::transformation_trait and seqan3::unary_type_trait.
Provides seqan3::views::convert.
Hide me