module Shrub where
import Data.List
import Data.Char
data Shrub a = Branch !(Shrub a) !(Shrub a) !(Shrub a) !(Shrub a) | Leaf !a | Empty deriving (Show)
addShrub :: Shrub a -> String -> a -> Shrub a
addShrub _ [] v = Leaf v
addShrub sb@(Branch a c g t) ('A':sq) v = Branch (addShrub a sq v) c g t
addShrub sb@(Branch a c g t) ('C':sq) v = Branch a (addShrub c sq v) g t
addShrub sb@(Branch a c g t) ('G':sq) v = Branch a c (addShrub g sq v) t
addShrub sb@(Branch a c g t) ('T':sq) v = Branch a c g (addShrub t sq v)
addShrub Empty ('A':sq) v = Branch (addShrub Empty sq v) Empty Empty Empty
addShrub Empty ('C':sq) v = Branch Empty (addShrub Empty sq v) Empty Empty
addShrub Empty ('G':sq) v = Branch Empty Empty (addShrub Empty sq v) Empty
addShrub Empty ('T':sq) v = Branch Empty Empty Empty (addShrub Empty sq v)
addShrub (Leaf _) l v = addShrub Empty l v
addShrubDegen :: Shrub a -> String -> a -> Shrub a
addShrubDegen _ [] v = Leaf v
addShrubDegen sb@(Branch a c g t) (b:sq) v | isUpper b = branch b
| isLower b = branch $ toUpper b where
addA = (addShrubDegen a sq v)
addC = (addShrubDegen c sq v)
addG = (addShrubDegen g sq v)
addT = (addShrubDegen t sq v)
branch b = case b of
'A' -> Branch addA c g t
'C' -> Branch a addC g t
'G' -> Branch a c addG t
'T' -> Branch a c g addT
'M' -> Branch addA addC g t
'Y' -> Branch a addC g addT
'R' -> Branch addA c addG t
'K' -> Branch a c addG addT
'S' -> Branch a addC addG t
'W' -> Branch addA c g addT
'B' -> Branch a addC addG addT
'V' -> Branch addA addC addG t
'D' -> Branch addA c addG addT
'H' -> Branch addA addC g addT
'I' -> Branch addA addC addG addT
'N' -> Branch addA addC addG addT
addShrubDegen Empty (b:sq) v | isUpper b = branch b
| isLower b = branch $ toUpper b where
rest = addShrubDegen Empty sq v
branch b = case b of
'A' -> Branch rest Empty Empty Empty
'C' -> Branch Empty rest Empty Empty
'G' -> Branch Empty Empty rest Empty
'T' -> Branch Empty Empty Empty rest
'M' -> Branch rest rest Empty Empty
'Y' -> Branch Empty rest Empty rest
'R' -> Branch rest Empty rest Empty
'K' -> Branch Empty Empty rest rest
'S' -> Branch Empty rest rest Empty
'W' -> Branch rest Empty Empty rest
'B' -> Branch Empty rest rest rest
'H' -> Branch rest rest Empty rest
'V' -> Branch rest rest rest Empty
'D' -> Branch rest Empty rest rest
'N' -> Branch rest rest rest rest
'I' -> Branch rest rest rest rest
addShrubDegen (Leaf _) l v = addShrubDegen Empty l v
subtractMultiple :: Shrub a -> [String] -> Shrub a
subtractMultiple sb [] = sb
subtractMultiple sb (x:xs) = subtractMultiple (subtractShrubDegen sb x) xs
subtractShrubDegen :: Shrub a -> String -> Shrub a
subtractShrubDegen Empty _ = Empty
subtractShrubDegen v@(Leaf _) _ = Empty
subtractShrubDegen sb@(Branch _ _ _ _) [] = sb
subtractShrubDegen sb@(Branch a c g t) (b:xs) =
let empt :: Shrub a -> Shrub a
empt (Branch Empty Empty Empty Empty) = Empty
empt oth = oth
in case b of
'A' -> empt $ Branch (subtractShrubDegen a xs) c g t
'C' -> empt $ Branch a (subtractShrubDegen c xs) g t
'G' -> empt $ Branch a c (subtractShrubDegen g xs) t
'T' -> empt $ Branch a c g (subtractShrubDegen t xs)
'I' -> empt $ Branch (subtractShrubDegen a xs) (subtractShrubDegen c xs)
(subtractShrubDegen g xs) (subtractShrubDegen t xs)
fromListDegen :: [(String, a)] -> Shrub a
fromListDegen = loop Empty where
loop sb [] = sb
loop sb ((sq, v):xs) = loop (addShrubDegen sb sq v) xs
fromList :: [(String, a)] -> Shrub a
fromList = loop Empty where
loop sb [] = sb
loop sb ((sq, v):xs) = loop (addShrub sb sq v) xs
searchShrub sb sq m = nubMax $ searchShrub' sb sq m
searchShrub' :: Shrub a -> String -> Int -> [(Int,a)]
searchShrub' Empty _ _ = []
searchShrub' (Leaf v) [] n = [(n,v)]
searchShrub' (Branch a c g t) [] n = concatMap (\q -> searchShrub' q [] n) [a,c,g,t]
searchShrub' (Leaf v) l n = [(n,v)]
searchShrub' sb@(Branch a c g t) l@(x:xs) n =
let perfmatch = case x of
'A' -> searchShrub' a xs n
'C' -> searchShrub' c xs n
'G' -> searchShrub' g xs n
'T' -> searchShrub' t xs n
otherwise -> []
indels = concatMap (\q -> searchShrub' q l (n-1)) [a,c,g,t] ++ case l of
(_:_) -> searchShrub' sb xs (n-1)
_ -> []
subs = case x of
'A' -> concatMap (\q -> searchShrub' q xs (n-1)) [c,g,t]
'C' -> concatMap (\q -> searchShrub' q xs (n-1)) [a,g,t]
'G' -> concatMap (\q -> searchShrub' q xs (n-1)) [a,c,t]
'T' -> concatMap (\q -> searchShrub' q xs (n-1)) [a,c,g]
otherwise -> concatMap (\q -> searchShrub' q xs (n-1)) [a,c,g,t]
in perfmatch ++ if n > 0 then subs else []
perfMatch' :: Shrub a -> String -> Int -> [(Int,a)]
perfMatch' (Branch a c g t) (x:xs) n = case x of
'A' -> searchShrub' a xs n
'C' -> searchShrub' c xs n
'G' -> searchShrub' g xs n
'T' -> searchShrub' t xs n
otherwise -> []
searchShrub'' :: Shrub a -> String -> Int -> Int -> [(Int,a)]
searchShrub'' Empty _ _ _ = []
searchShrub'' (Leaf v) [] n _ = [(n,v)]
searchShrub'' (Branch a c g t) [] n nid = concatMap (\q -> searchShrub'' q [] n nid) [a,c,g,t]
searchShrub'' (Leaf v) l n _ = [(n,v)]
searchShrub'' sb@(Branch a c g t) l@(x:xs) n nid =
let perfmatch = case x of
'A' -> searchShrub'' a xs n nid
'C' -> searchShrub'' c xs n nid
'G' -> searchShrub'' g xs n nid
'T' -> searchShrub'' t xs n nid
otherwise -> []
indels = concatMap (\q -> searchShrub'' q l (n-1) (nid-1)) [a,c,g,t] ++ case l of
(_:_) -> searchShrub'' sb xs (n-1) (nid-1)
_ -> []
subs = case x of
'A' -> concatMap (\q -> searchShrub'' q xs (n-1) nid) [c,g,t]
'C' -> concatMap (\q -> searchShrub'' q xs (n-1) nid) [a,g,t]
'G' -> concatMap (\q -> searchShrub'' q xs (n-1) nid) [a,c,t]
'T' -> concatMap (\q -> searchShrub'' q xs (n-1) nid) [a,c,g]
otherwise -> concatMap (\q -> searchShrub'' q xs (n-1) nid) [a,c,g,t]
in perfmatch ++ if n > 0 then subs ++ if (nid > 0) then indels else [] else []
-- | Search Shrub with constraint to ignore a result
searchShrubNE :: Eq a => Shrub a -> String -> a -> Int -> Int -> [(Int,a)]
searchShrubNE Empty _ _ _ _ = []
searchShrubNE (Leaf v) [] om n _ | v == om = []
|otherwise = [(n,v)]
searchShrubNE (Branch a c g t) [] om n nid = concatMap (\q -> searchShrubNE q [] om n nid) [a,c,g,t]
searchShrubNE (Leaf v) l om n _ | v == om = []
|otherwise = [(n,v)]
searchShrubNE sb@(Branch a c g t) l@(x:xs) om n nid =
let perfmatch = case x of
'A' -> searchShrubNE a xs om n nid
'C' -> searchShrubNE c xs om n nid
'G' -> searchShrubNE g xs om n nid
'T' -> searchShrubNE t xs om n nid
otherwise -> []
freeindel = nid > 0
n' = if freeindel then n-1 else n-2
nid' = if freeindel then nid-1 else nid'
indels = if not freeindel && n < 2 then [] else
if n' < 0 then [] else case l of
(_:_:xss) -> concatMap (\q -> searchShrubNE q l om n' nid') [a, c, g, t] ++
concatMap (\q -> searchShrubNE q xss om n' nid') [a, c, g, t]
_ -> concatMap (\q -> searchShrubNE q l om n' nid') [a, c, g, t]
subs = case x of
'A' -> concatMap (\q -> searchShrubNE q xs om (n-1) nid) [c,g,t]
'C' -> concatMap (\q -> searchShrubNE q xs om (n-1) nid) [a,g,t]
'G' -> concatMap (\q -> searchShrubNE q xs om (n-1) nid) [a,c,t]
'T' -> concatMap (\q -> searchShrubNE q xs om (n-1) nid) [a,c,g]
otherwise -> concatMap (\q -> searchShrubNE q xs om (n-1) nid) [a,c,g,t]
in if n == 0 then perfmatch else perfmatch ++ subs ++ indels where
-- | Give you nid 1 cost indel, then remaining 2 cost indels
searchShrub3 :: Shrub a -> String -> Int -> Int -> [(Int,a)]
searchShrub3 Empty _ _ _ = []
searchShrub3 (Leaf v) [] n _ = [(n,v)]
searchShrub3 (Branch a c g t) [] n nid = concatMap (\q -> searchShrub3 q [] n nid) [a,c,g,t]
searchShrub3 (Leaf v) l n _ = [(n,v)]
searchShrub3 sb@(Branch a c g t) l@(x:xs) n nid =
let perfmatch = case x of
'A' -> searchShrub3 a xs n nid
'C' -> searchShrub3 c xs n nid
'G' -> searchShrub3 g xs n nid
'T' -> searchShrub3 t xs n nid
'I' -> concatMap (\q -> searchShrub3 q xs n nid) [a,c,g,t]
otherwise -> []
freeindel = nid > 0
n' = if freeindel then n-1 else n-2
nid' = if freeindel then nid-1 else nid
indels = if not freeindel && n < 2 then [] else
if n' < 0 then [] else concatMap (\q -> searchShrub3 q l n' nid') [a,c,g,t] ++ case l of
(_:_:xss) -> searchShrub3 sb xss n' nid'
_ -> concatMap (\q -> searchShrub3 q l n' nid') [a,c,g,t]
subs = case x of
'A' -> concatMap (\q -> searchShrub3 q xs (n-1) nid) [c,g,t]
'C' -> concatMap (\q -> searchShrub3 q xs (n-1) nid) [a,g,t]
'G' -> concatMap (\q -> searchShrub3 q xs (n-1) nid) [a,c,t]
'T' -> concatMap (\q -> searchShrub3 q xs (n-1) nid) [a,c,g]
'I' -> []
otherwise -> concatMap (\q -> searchShrub3 q xs (n-1) nid) [a,c,g,t]
in if n == 0 then perfmatch else perfmatch ++ subs ++ indels
-- | Melting point shrub search
searchShrubTM :: Int -> Shrub a -> String -> Int -> [(Int,a)]
searchShrubTM _ Empty _ _ = []
searchShrubTM thr (Leaf v) [] n | n >= thr = [(n,v)]
| otherwise = []
searchShrubTM thr (Branch a c g t) [] n = concatMap (\q -> searchShrubTM thr q [] n) [a,c,g,t]
searchShrubTM thr (Leaf v) l n | n >= thr = [(n,v)]
| otherwise = []
searchShrubTM thr sb@(Branch a c g t) l@(x:xs) n | n >= thr = concatMap (\q -> searchShrubTM thr q [] n) [a,c,g,t]
| otherwise =
let ssbt = searchShrubTM thr
perfmatch = case x of
'A' -> ssbt a xs (n+1)
'C' -> ssbt c xs (n+2)
'G' -> ssbt g xs (n+2)
'T' -> ssbt t xs (n+1)
otherwise -> []
indels = concatMap (\q -> ssbt q l (n-3)) [a,c,g,t] ++ case l of
(_:_:xss) -> ssbt sb xss (n-3)
_ -> []
subs = case x of
'A' -> concatMap (\q -> ssbt q xs (n-2)) [c,g,t]
'C' -> concatMap (\q -> ssbt q xs (n-2)) [a,g,t]
'G' -> concatMap (\q -> ssbt q xs (n-2)) [a,c,t]
'T' -> concatMap (\q -> ssbt q xs (n-2)) [a,c,g]
'I' -> concatMap (\q -> ssbt q xs (n-1)) [a,c,g,t]
otherwise -> concatMap (\q -> ssbt q xs (n-2)) [a,c,g,t]
in perfmatch ++ subs ++ indels
searchShrubPN :: Int -> Shrub a -> String -> Int -> [(Int,a)]
searchShrubPN _ Empty _ _ = []
searchShrubPN _ (Leaf v) [] n = [(n,v)]
searchShrubPN _ (Branch a c g t) [] n = concatMap (\q -> searchShrubPN 0 q [] n) [a,c,g,t]
searchShrubPN _ (Leaf v) l n = [(n,v)]
searchShrubPN pr sb@(Branch a c g t) l@(x:xs) n =
let ssp = searchShrubPN pr'
pr' = if pr > 0 then pr-1 else pr
indels = concatMap (\q -> ssp q l (n-1)) [a,c,g,t] ++ case l of
(_:_) -> ssp sb xs (n-1)
_ -> []
subs = case x of
'A' -> concatMap (\q -> ssp q xs (n-1)) [c,g,t]
'C' -> concatMap (\q -> ssp q xs (n-1)) [a,g,t]
'G' -> concatMap (\q -> ssp q xs (n-1)) [a,c,t]
'T' -> concatMap (\q -> ssp q xs (n-1)) [a,c,g]
'I' -> concatMap (\q -> ssp q xs n) [a,c,g,t]
otherwise -> concatMap (\q -> ssp q xs (n-1)) [a,c,g,t]
perfmatch = case x of
'A' -> ssp a xs n
'C' -> ssp c xs n
'G' -> ssp g xs n
'T' -> ssp t xs n
otherwise -> []
in perfmatch ++ if n == 0 || pr > 0 then [] else subs ++ indels
searchShrubTK :: Int -> Shrub a -> String -> Int -> [(Int,a)]
searchShrubTK _ Empty _ _ = []
searchShrubTK _ (Leaf v) [] n = [(n,v)]
searchShrubTK _ (Branch a c g t) [] n = concatMap (\q -> searchShrubTK 0 q [] n) [a,c,g,t]
searchShrubTK 0 (Branch a c g t) _ n = concatMap (\q -> searchShrubTK 0 q [] n) [a,c,g,t]
searchShrubTK _ (Leaf v) l n = [(n,v)]
searchShrubTK tk sb@(Branch a c g t) l@(x:xs) n =
let ssp = searchShrubTK tk'
tk' = tk - 1
indels = concatMap (\q -> ssp q l (n-1)) [a,c,g,t] ++ case xs of
(_:_) -> searchShrubTK tk sb xs (n-1)
_ -> []
subs = case x of
'A' -> concatMap (\q -> ssp q xs (n-1)) [c,g,t]
'C' -> concatMap (\q -> ssp q xs (n-1)) [a,g,t]
'G' -> concatMap (\q -> ssp q xs (n-1)) [a,c,t]
'T' -> concatMap (\q -> ssp q xs (n-1)) [a,c,g]
'I' -> concatMap (\q -> ssp q xs n) [a,c,g,t]
otherwise -> concatMap (\q -> ssp q xs (n-1)) [a,c,g,t]
perfmatch = case x of
'A' -> ssp a xs n
'C' -> ssp c xs n
'G' -> ssp g xs n
'T' -> ssp t xs n
otherwise -> []
in perfmatch ++ if n > 0 then subs ++ indels else []
searchShrubTK2 :: Int -> Shrub a -> String -> Int -> Int -> [(Int,a)]
searchShrubTK2 _ Empty _ _ _ = []
searchShrubTK2 _ (Leaf v) [] n _ = [(n,v)]
searchShrubTK2 _ (Branch a c g t) [] n nid = concatMap (\q -> searchShrubTK2 0 q [] n nid) [a,c,g,t]
searchShrubTK2 0 (Branch a c g t) _ n nid = concatMap (\q -> searchShrubTK2 0 q [] n nid) [a,c,g,t]
searchShrubTK2 _ (Leaf v) _ n _ = [(n,v)]
searchShrubTK2 tk sb@(Branch a c g t) l@(x:xs) n nid =
let ssp = searchShrubTK2 tk'
tk' = tk - 1
indels = if nid < 1 then [] else concatMap (\q -> searchShrubTK2 tk q l (n-1) (nid-1)) [a,c,g,t] ++ case l of
(_:_) -> searchShrubTK2 tk sb xs (n-1) (nid-1)
_ -> []
subs = case x of
'A' -> concatMap (\q -> ssp q xs (n-1) nid) [c,g,t]
'C' -> concatMap (\q -> ssp q xs (n-1) nid) [a,g,t]
'G' -> concatMap (\q -> ssp q xs (n-1) nid) [a,c,t]
'T' -> concatMap (\q -> ssp q xs (n-1) nid) [a,c,g]
'I' -> concatMap (\q -> ssp q xs n nid) [a,c,g,t]
otherwise -> concatMap (\q -> ssp q xs (n-1) nid) [a,c,g,t]
perfmatch = case x of
'A' -> ssp a xs n nid
'C' -> ssp c xs n nid
'G' -> ssp g xs n nid
'T' -> ssp t xs n nid
otherwise -> []
in perfmatch ++ if n > 0 then subs ++ indels else []
searchShrubTK3 :: Int -> Shrub a -> String -> Int -> Int -> [(Int,a)]
searchShrubTK3 _ Empty _ _ _ = []
searchShrubTK3 _ (Leaf v) [] n _ = [(n,v)]
searchShrubTK3 _ (Branch a c g t) [] n nid = concatMap (\q -> searchShrubTK3 0 q [] n nid) [a,c,g,t]
searchShrubTK3 0 (Branch a c g t) _ n nid = concatMap (\q -> searchShrubTK3 0 q [] n nid) [a,c,g,t]
searchShrubTK3 _ (Leaf v) _ n _ = [(n,v)]
searchShrubTK3 tk sb@(Branch a c g t) l@(x:xs) n nid =
let ssp = searchShrubTK3 tk'
tk' = tk - 1
freeindel = nid > 0
n' = if freeindel then n-1 else n-2
nid' = if freeindel then nid-1 else nid
indels = if n' < 0 then [] else concatMap (\q -> searchShrubTK3 tk' q l n' nid') [a,c,g,t] ++ case l of
(_:_) -> searchShrubTK3 tk sb xs n' nid'
_ -> []
subs = case x of
'A' -> concatMap (\q -> ssp q xs (n-1) nid) [c,g,t]
'C' -> concatMap (\q -> ssp q xs (n-1) nid) [a,g,t]
'G' -> concatMap (\q -> ssp q xs (n-1) nid) [a,c,t]
'T' -> concatMap (\q -> ssp q xs (n-1) nid) [a,c,g]
'I' -> concatMap (\q -> ssp q xs n nid) [a,c,g,t]
otherwise -> concatMap (\q -> ssp q xs (n-1) nid) [a,c,g,t]
perfmatch = case x of
'A' -> ssp a xs n nid
'C' -> ssp c xs n nid
'G' -> ssp g xs n nid
'T' -> ssp t xs n nid
otherwise -> []
in perfmatch ++ if n > 0 then subs ++ indels else []
searchShrubXF :: Shrub a -> String -> Int -> Bool -> [(Int,a)]
searchShrubXF Empty _ _ _ = []
searchShrubXF (Leaf v) _ n bul = if bul then [(n,v)] else []
searchShrubXF (Branch a c g t) [] n _ = []
searchShrubXF sb@(Branch a c g t) l@(x:xs) n _ =
let perfmatch = case x of
'A' -> searchShrubXF a xs n True
'C' -> searchShrubXF c xs n True
'G' -> searchShrubXF g xs n True
'T' -> searchShrubXF t xs n True
otherwise -> []
indels = concatMap (\q -> searchShrubXF q l (n-1) False) [a,c,g,t] ++ case l of
(_:_) -> searchShrubXF sb xs (n-1) False
_ -> []
subs = case x of
'A' -> concatMap (\q -> searchShrubXF q xs (n-1) False) [c,g,t]
'C' -> concatMap (\q -> searchShrubXF q xs (n-1) False) [a,g,t]
'G' -> concatMap (\q -> searchShrubXF q xs (n-1) False) [a,c,t]
'T' -> concatMap (\q -> searchShrubXF q xs (n-1) False) [a,c,g]
otherwise -> concatMap (\q -> searchShrubXF q xs (n-1) False) [a,c,g,t]
in perfmatch ++ if n > 0 then subs else []
-- | IonTorrent Shrub search
searchShrubIT :: Shrub a -> String -> Int -> [(Int, (a, String))]
searchShrubIT Empty _ _ = []
searchShrubIT (Leaf v) s n = [(n, (v, s))]
searchShrubIT (Branch a c g t) [] n = [] --concatMap (\q -> searchShrubIT q [] n) [a,c,g,t]
searchShrubIT sb@(Branch a c g t) l@(x:xs) n | n > 0 = perfmatch ++ subs ++ indels
| otherwise = perfmatch where
perfmatch = case x of
'A' -> searchShrubIT a xs n
'C' -> searchShrubIT c xs n
'G' -> searchShrubIT g xs n
'T' -> searchShrubIT t xs n
otherwise -> []
indels = concatMap (\q -> searchShrubIT q l (n-1)) [a,c,g,t] ++ searchShrubIT sb xs (n-1)
subs = case x of
'A' -> concatMap (\q -> searchShrubIT q xs (n-3)) [c,g,t]
'C' -> concatMap (\q -> searchShrubIT q xs (n-3)) [a,g,t]
'G' -> concatMap (\q -> searchShrubIT q xs (n-3)) [a,c,t]
'T' -> concatMap (\q -> searchShrubIT q xs (n-3)) [a,c,g]
otherwise -> concatMap (\q -> searchShrubIT q xs (n-3)) [a,c,g,t]
nubMax :: (Ord a, Eq b) => [(a,b)] -> [(a,b)]
nubMax = foldl' go [] where
go l i@(m, iv) = maybe (i:l) (\fn -> if m > fst (l !! fn) then i:(take fn l ++ drop (fn+1) l) else l) (findIndex (\(p, q) -> iv == q) l)
--nubMax' :: (Ord a, Eq b) => [(a,b)] -> [(a,b)]
--nubMax' = map (uncurry (flip (,))) . HM.toList $ foldl' go HM.empty where
--go hm i@(m, iv) = maybe (HM.insert iv m hm) (\fn -> if m > fn then HM.insert iv m hm else hm) (HM.lookup iv hm)
searchShrubCount :: Shrub a -> String -> Int -> [(Int,Int,a)]
searchShrubCount sb sq mm = sshrub sb sq 0 mm where
sshrub Empty _ _ _ = []
sshrub (Leaf v) [] cnt n = [(n,cnt,v)]
sshrub (Branch a c g t) [] cnt n = concatMap (\q -> sshrub q [] cnt n) [a,c,g,t]
sshrub (Leaf v) l cnt n = [(n,cnt,v)]
sshrub sb@(Branch a c g t) l@(x:xs) cnt n =
let cnt' = cnt + 1
perfmatch = case x of
'A' -> sshrub a xs cnt' n
'C' -> sshrub c xs cnt' n
'G' -> sshrub g xs cnt' n
'T' -> sshrub t xs cnt' n
otherwise -> []
indels = concatMap (\q -> sshrub q l cnt (n-1)) [a,c,g,t] ++ case l of
(_:_) -> sshrub sb xs cnt' (n-1)
_ -> []
subs = case x of
'A' -> concatMap (\q -> sshrub q xs cnt' (n-1)) [c,g,t]
'C' -> concatMap (\q -> sshrub q xs cnt' (n-1)) [a,g,t]
'G' -> concatMap (\q -> sshrub q xs cnt' (n-1)) [a,c,t]
'T' -> concatMap (\q -> sshrub q xs cnt' (n-1)) [a,c,g]
otherwise -> concatMap (\q -> sshrub q xs cnt' (n-1)) [a,c,g,t]
in perfmatch ++ if n > 0 then subs else []