debruijn/
clean_graph.rs

1// Copyright 2017 10x Genomics
2
3//! DeBruijn graph simplification routines. Currently tip-removal is implemented.
4use crate::graph::{DebruijnGraph, Node};
5use crate::Kmer;
6use std::fmt::Debug;
7use std::marker::PhantomData;
8
9pub struct CleanGraph<K: Kmer, D, T1>
10where
11    T1: Fn(&Node<'_, K, D>) -> bool,
12{
13    tip_predicate: T1,
14    _k: PhantomData<K>,
15    _d: PhantomData<D>,
16}
17
18impl<K: Kmer, D: Debug, T1> CleanGraph<K, D, T1>
19where
20    T1: Fn(&Node<'_, K, D>) -> bool,
21{
22    pub fn new(tip_predicate: T1) -> CleanGraph<K, D, T1> {
23        CleanGraph {
24            tip_predicate,
25            _k: PhantomData,
26            _d: PhantomData,
27        }
28    }
29
30    fn test_tip(&self, graph: &DebruijnGraph<K, D>, id: usize) -> Option<usize> {
31        let node = graph.get_node(id);
32        let exts = node.exts();
33        if exts.num_exts_r() > 0 && exts.num_exts_l() > 0 {
34            return None;
35        }
36
37        if ((exts.num_exts_l() == 0 && exts.num_exts_r() <= 1)
38            || (exts.num_exts_r() == 0 && exts.num_exts_l() <= 1))
39            && (self.tip_predicate)(&node)
40        {
41            return Some(id);
42        }
43
44        None
45    }
46
47    pub fn find_bad_nodes(&self, graph: &DebruijnGraph<K, D>) -> Vec<usize> {
48        (0..graph.len())
49            .filter_map(|i| self.test_tip(graph, i))
50            .collect()
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use crate::{build_test_graph, clean_graph::CleanGraph, graph::Node, kmer::Kmer16, summarizer::TagsCountsData};
57
58    #[test]
59    fn test_clean_graph() {
60        let (_ser_reads, _ser_kmers, ser_graph) = build_test_graph::<Kmer16, TagsCountsData, _>();
61        let cleaner = CleanGraph::<Kmer16, TagsCountsData, _>::new(|node: &Node<'_, _, TagsCountsData>| (node.l_edges().is_empty() | node.r_edges().is_empty()) & (node.data().sum() == 1));
62        let bad_nodes = cleaner.find_bad_nodes(ser_graph.graph());
63        assert_eq!(vec![4, 18, 20, 23, 34, 44, 66, 73, 76, 88], bad_nodes);
64    }
65}
debruijn/clean_graph.rs

debruijn/
clean_graph.rs
