Derive a tighter bound for the branch-and-bound strategy for the median string problem. Hint: Split an l-mer w into two parts, u and v. Use totalDistance(u, DNA) + totalDistance(v, DNA) to bound totalDistance(w, DNA).

Above is the branch and bound strategy for the median string problem. I know that distance(u) + distance(v) BRANCHANDBOUNDMEDIANSEARCH(DNA,t, n, l) 2 bestDistanceoo 4 while i> 0 6 prefix nucleotide string corresponding to (s1, s2-.. , si optimisticDistance TOTALDISTANCE (prefix, DNA) if optimisticDistance > bestDistance 7 (s, i) BYPASS(si, 1, 4) 10 else (s, i) NEXTVERTEX(s, 2.1.4) else 12 13 14 15 16 17 18 return bestWord word nucleotide string corresponding to (s1, 82, . . s1) if TOTALDISTANCE(word, DNA) 0 6 prefix nucleotide string corresponding to (s1, s2-.. , si optimisticDistance TOTALDISTANCE (prefix, DNA) if optimisticDistance > bestDistance 7 (s, i) BYPASS(si, 1, 4) 10 else (s, i) NEXTVERTEX(s, 2.1.4) else 12 13 14 15 16 17 18 return bestWord word nucleotide string corresponding to (s1, 82, . . s1) if TOTALDISTANCE(word, DNA)