//Use Hirschberg's algorithm to align two sequences. (More efficient than NW.)
Use Hirschberg's algorithm to align two sequences. (More efficient than NW.)
Use Hirschberg ' s algorithm to align two sequences . ( More efficient than NW . )
pub fn align<M : Fn(Nucleotide, Nucleotide)-> i64, C : Fn(i64)->i64>(a : &Sequence, b : &Sequence, sub_matrix : Rc<M>, cost_func : Rc<C>) -> (Sequence, Sequence) {
        //Get the sequences. 
        let s = &a.nucleotides; 
        let t = &b.nucleotides;
        //Base cases. 
        if s.len() == 0 {
            let a = Sequence::from_nucleotides(vec!(Gap; t.len()));
            let b = Sequence::from_nucleotides(t.to_vec()); 
            return (a, b);
        }
        if t.len() == 0 {
            let a = Sequence::from_nucleotides(s.to_vec()); 
            let b = Sequence::from_nucleotides(vec!(Gap; s.len()));
            return (a, b);
        }
        if t.len() == 1 || s.len() == 1 {
            let (a, b, _) = needleman_wunsch(a, b, sub_matrix, cost_func); 
            return (a, b);
        }
        //Split S. 
        let s_split : usize = s.len()/2; 
        let sl = s[..s_split].to_vec(); 
        let mut sr = s[s_split..].to_vec(); 
        //Figure out where to split t. 
        let mut t_prime = t.clone(); 
        t_prime.reverse(); 
        sr.reverse(); 
        let n1 = low_mem_nw(&b, &Sequence::from_nucleotides(sl.clone()), Rc::clone(&sub_matrix), Rc::clone(&cost_func));
        let mut n2 = low_mem_nw(&Sequence::from_nucleotides(t_prime), &Sequence::from_nucleotides(sr.clone()), Rc::clone(&sub_matrix), Rc::clone(&cost_func));
        sr.reverse(); 
        n2.reverse(); 
        //Find best split for t.
        let pairs = n1.iter().zip(n2.iter()).map(|(a,b)| a+b).enumerate();
        let t_split = match pairs.max_by_key(|(_i,v)| *v) {
            Some((i, _v)) => i, 
            None => 0
        };
        let tl = t[..t_split].to_vec(); 
        let tr = t[t_split..].to_vec(); 
        //Recursive call.
        let (xl, zl) = align(&Sequence::from_nucleotides(sl), &Sequence::from_nucleotides(tl), Rc::clone(&sub_matrix), Rc::clone(&cost_func));
        let (xr, zr) = align(&Sequence::from_nucleotides(sr), &Sequence::from_nucleotides(tr), Rc::clone(&sub_matrix), Rc::clone(&cost_func));
        return (xl.concat(&xr), zl.concat(&zr));
    }
pub fn align < M : Fn ( Nucleotide , Nucleotide ) -> i64 , C : Fn ( i64 ) -> i64 > ( a : & Sequence , b : & Sequence , sub_matrix : Rc < M > , cost_func : Rc < C > ) -> ( Sequence , Sequence ) { //Get the sequences.  let s = & a . nucleotides ; let t = & b . nucleotides ; //Base cases.  if s . len ( ) == 0 { let a = Sequence :: from_nucleotides ( vec ! ( Gap t len ( ) ) ) ; let b = Sequence :: from_nucleotides ( t . to_vec ( ) ) ; return ( a , b ) ; } if t . len ( ) == 0 { let a = Sequence :: from_nucleotides ( s . to_vec ( ) ) ; let b = Sequence :: from_nucleotides ( vec ! ( Gap s len ( ) ) ) ; return ( a , b ) ; } if t . len ( ) == 1 || s . len ( ) == 1 { let ( a , b , _ ) = needleman_wunsch ( a , b , sub_matrix , cost_func ) ; return ( a , b ) ; } //Split S.  let s_split : usize = s . len ( ) / 2 ; let sl = s [ .. s_split ] . to_vec ( ) ; let mut sr = s [ s_split .. ] . to_vec ( ) ; //Figure out where to split t.  let mut t_prime = t . clone ( ) ; t_prime . reverse ( ) ; sr . reverse ( ) ; let n1 = low_mem_nw ( & b , & Sequence :: from_nucleotides ( sl . clone ( ) ) , Rc :: clone ( & sub_matrix ) , Rc :: clone ( & cost_func ) ) ; let mut n2 = low_mem_nw ( & Sequence :: from_nucleotides ( t_prime ) , & Sequence :: from_nucleotides ( sr . clone ( ) ) , Rc :: clone ( & sub_matrix ) , Rc :: clone ( & cost_func ) ) ; sr . reverse ( ) ; n2 . reverse ( ) ; //Find best split for t. let pairs = n1 . iter ( ) . zip ( n2 . iter ( ) ) . map ( | ( a , b ) | a + b ) . enumerate ( ) ; let t_split = match pairs . max_by_key ( | ( _i , v ) | * v ) { Some ( ( i , _v ) ) => i , None => 0 } ; let tl = t [ .. t_split ] . to_vec ( ) ; let tr = t [ t_split .. ] . to_vec ( ) ; //Recursive call. let ( xl , zl ) = align ( & Sequence :: from_nucleotides ( sl ) , & Sequence :: from_nucleotides ( tl ) , Rc :: clone ( & sub_matrix ) , Rc :: clone ( & cost_func ) ) ; let ( xr , zr ) = align ( & Sequence :: from_nucleotides ( sr ) , & Sequence :: from_nucleotides ( tr ) , Rc :: clone ( & sub_matrix ) , Rc :: clone ( & cost_func ) ) ; return ( xl . concat ( & xr ) , zl . concat ( & zr ) ) ; }
Use Hirschberg's algorithm to align two sequences.
Use Hirschberg ' s algorithm to align two sequences .
a
&Sequence
b
&Sequence
sub_matrix
Rc<M>
cost_func
Rc<C>