seed_chain 0.9.0

A seeding and generic chaining mechanism for sequence-to-sequence alignment
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

use generic_a_star::{cost::AStarCost, reset::Reset, AStarContext, AStarNode};

use crate::seed::ChainingAnchors;

use super::node::{Identifier, Node};

pub trait ChainingCostsProvider {
    type Cost: AStarCost;

    /// Returns the cost of chaining `to` after `from`.
    ///
    /// If the chaining is impossible, then `Cost::MAX` is returned.
    fn chaining_costs(&self, from: &Identifier, to: &Identifier) -> Self::Cost;
}

pub struct Context<ChainingCosts: ChainingCostsProvider> {
    chaining_costs: ChainingCosts,
    chaining_anchors: ChainingAnchors,
}

impl<ChainingCosts: ChainingCostsProvider> AStarContext for Context<ChainingCosts> {
    type Node = Node<<ChainingCosts as ChainingCostsProvider>::Cost>;

    fn create_root(&self) -> Self::Node {
        Self::Node::new_root()
    }

    fn generate_successors(&mut self, node: &Self::Node, output: &mut impl Extend<Self::Node>) {
        // We skip all anchors whose reference block is not right of the current node.
        let first_chainable_block_index = match node.identifier() {
            Identifier::Root => 0,
            Identifier::Anchor { anchor } => {
                self.chaining_anchors
                    .anchors()
                    .partition_point(|chaining_anchor| {
                        // We do not allow to chain overlapping blocks.
                        chaining_anchor.reference_block().start < anchor.reference_block().end
                    })
            }
            Identifier::Target => self.chaining_anchors.anchors().len(),
        };

        output.extend(
            self.chaining_anchors
                .anchors()
                .iter()
                .skip(first_chainable_block_index)
                .filter_map(|chaining_anchor| {
                    // We skip all anchors whose query block is not right of the current node.
                    if let Identifier::Anchor { anchor } = node.identifier() {
                        if chaining_anchor.query_block().start < anchor.query_block().end {
                            return None;
                        }
                    }

                    let successor_identifier = Identifier::Anchor {
                        anchor: chaining_anchor.clone(),
                    };
                    let cost_increment = self
                        .chaining_costs
                        .chaining_costs(node.identifier(), &successor_identifier);
                    node.generate_successor(successor_identifier, cost_increment)
                })
                .chain(if !matches!(node.identifier(), Identifier::Target) {
                    node.generate_successor(
                        Identifier::Target,
                        self.chaining_costs
                            .chaining_costs(node.identifier(), &Identifier::Target),
                    )
                } else {
                    None
                }),
        );
    }

    fn is_target(&self, node: &Self::Node) -> bool {
        matches!(node.identifier(), Identifier::Target)
    }

    fn cost_limit(&self) -> Option<<Self::Node as AStarNode>::Cost> {
        None
    }

    fn memory_limit(&self) -> Option<usize> {
        None
    }
}

impl<ChainingCosts: ChainingCostsProvider> Context<ChainingCosts> {
    pub fn new(chaining_costs: ChainingCosts, chaining_anchors: ChainingAnchors) -> Self {
        Self {
            chaining_costs,
            chaining_anchors,
        }
    }
}

impl<ChainingCosts: ChainingCostsProvider> Reset for Context<ChainingCosts> {
    fn reset(&mut self) {
        todo!()
    }
}