Bioinformatics Algorithms

Problem 2.17

There are n bacteria and 1 virus in a Petri dish. Within the first minute, the virus kills one bacterium and produces another copy of itself, and all of the remaining bacteria reproduce, making 2 viruses and 2 · (n - 1) bacteria. In the second minute, each of the viruses kills a bacterium and produces a new copy of itself (resulting in 4 viruses and 2(2(n - 1) - 2) = 4n - 8 bacteria; again, the remaining bacteria reproduce. This process continues every minute. Will the viruses eventually kill all the bacteria? If so, design an algorithm that computes how many steps it will take. How does the running time of your algorithm depend on n?

Problem 4.13

Given a long text string T, one shorter pattern string s, and an integer k, find the first occurrence in T of a string (if any) s such that dH(s, s ) ≤ k. What is the complexity of your algorithm?

Problem 4.14

Given a long text string T, one shorter pattern string s, and an integer k, find the first occurrence in T of a string (if any) s such that dH(s, s ) ≤ k. What is the complexity of your algorithm?.

Tll these qustion are from the book (Introduction to Bioinformatics Algorithms. Neil C. Jones and Pavel A. Pevzner, The MIT Press (ISBN: 0-262-10106-8))