/// A global Needleman-Wunsch aligner on partially ordered graphs.
///
/// # Arguments
/// * `query` - the query TextSlice to align against the internal graph member
A global Needleman-Wunsch aligner on partially ordered graphs.
A global Needleman - Wunsch aligner on partially ordered graphs .
pub fn global(&self, query: TextSlice) -> Traceback {
        assert!(self.graph.node_count() != 0);
        // dimensions of the traceback matrix
        let (m, n) = (self.graph.node_count(), query.len());
        let mut traceback = Traceback::with_capacity(m, n);
        traceback.initialize_scores(self.scoring.gap_open);
        traceback.set(
            0,
            0,
            TracebackCell {
                score: 0,
                op: AlignmentOperation::Match(None),
            },
        );
        // construct the score matrix (O(n^2) space)
        let mut topo = Topo::new(&self.graph);
        while let Some(node) = topo.next(&self.graph) {
            // reference base and index
            let r = self.graph.raw_nodes()[node.index()].weight; // reference base at previous index
            let i = node.index() + 1;
            traceback.last = node;
            // iterate over the predecessors of this node
            let prevs: Vec<NodeIndex<usize>> =
                self.graph.neighbors_directed(node, Incoming).collect();
            // query base and its index in the DAG (traceback matrix rows)
            for (j_p, q) in query.iter().enumerate() {
                let j = j_p + 1;
                // match and deletion scores for the first reference base
                let max_cell = if prevs.is_empty() {
                    TracebackCell {
                        score: traceback.get(0, j - 1).score + self.scoring.match_fn.score(r, *q),
                        op: AlignmentOperation::Match(None),
                    }
                } else {
                    let mut max_cell = TracebackCell {
                        score: MIN_SCORE,
                        op: AlignmentOperation::Match(None),
                    };
                    for prev_node in &prevs {
                        let i_p: usize = prev_node.index() + 1; // index of previous node
                        max_cell = max(
                            max_cell,
                            max(
                                TracebackCell {
                                    score: traceback.get(i_p, j - 1).score
                                        + self.scoring.match_fn.score(r, *q),
                                    op: AlignmentOperation::Match(Some((i_p - 1, i - 1))),
                                },
                                TracebackCell {
                                    score: traceback.get(i_p, j).score + self.scoring.gap_open,
                                    op: AlignmentOperation::Del(Some((i_p - 1, i))),
                                },
                            ),
                        );
                    }
                    max_cell
                };
                let score = max(
                    max_cell,
                    TracebackCell {
                        score: traceback.get(i, j - 1).score + self.scoring.gap_open,
                        op: AlignmentOperation::Ins(Some(i - 1)),
                    },
                );
                traceback.set(i, j, score);
            }
        }
        traceback
    }
pub fn global ( & self , query : TextSlice ) -> Traceback { assert ! ( self graph node_count ( ) 0 ) ; // dimensions of the traceback matrix let ( m , n ) = ( self . graph . node_count ( ) , query . len ( ) ) ; let mut traceback = Traceback :: with_capacity ( m , n ) ; traceback . initialize_scores ( self . scoring . gap_open ) ; traceback . set ( 0 , 0 , TracebackCell { score : 0 , op : AlignmentOperation :: Match ( None ) , } , ) ; // construct the score matrix (O(n^2) space) let mut topo = Topo :: new ( & self . graph ) ; while let Some ( node ) = topo . next ( & self . graph ) { // reference base and index let r = self . graph . raw_nodes ( ) [ node . index ( ) ] . weight ; // reference base at previous index let i = node . index ( ) + 1 ; traceback . last = node ; // iterate over the predecessors of this node let prevs : Vec < NodeIndex < usize > > = self . graph . neighbors_directed ( node , Incoming ) . collect ( ) ; // query base and its index in the DAG (traceback matrix rows) for ( j_p , q ) in query . iter ( ) . enumerate ( ) { let j = j_p + 1 ; // match and deletion scores for the first reference base let max_cell = if prevs . is_empty ( ) { TracebackCell { score : traceback . get ( 0 , j - 1 ) . score + self . scoring . match_fn . score ( r , * q ) , op : AlignmentOperation :: Match ( None ) , } } else { let mut max_cell = TracebackCell { score : MIN_SCORE , op : AlignmentOperation :: Match ( None ) , } ; for prev_node in & prevs { let i_p : usize = prev_node . index ( ) + 1 ; // index of previous node max_cell = max ( max_cell , max ( TracebackCell { score : traceback . get ( i_p , j - 1 ) . score + self . scoring . match_fn . score ( r , * q ) , op : AlignmentOperation :: Match ( Some ( ( i_p - 1 , i - 1 ) ) ) , } , TracebackCell { score : traceback . get ( i_p , j ) . score + self . scoring . gap_open , op : AlignmentOperation :: Del ( Some ( ( i_p - 1 , i ) ) ) , } , ) , ) ; } max_cell } ; let score = max ( max_cell , TracebackCell { score : traceback . get ( i , j - 1 ) . score + self . scoring . gap_open , op : AlignmentOperation :: Ins ( Some ( i - 1 ) ) , } , ) ; traceback . set ( i , j , score ) ; } } traceback }
A global Needleman-Wunsch aligner on partially ordered graphs.
A global Needleman - Wunsch aligner on partially ordered graphs .
&self
query
TextSlice