Project #1 -- Motif Finding

• Goal
• Be familiar with the concept of Motif finding
• Be familiar with algorithms of exhaustive Search, greedy and CONSENSUS
• Let you think the problem and solution thoroughly
• Project Description & Requirements
1. Please write the following motif finding programs to get the consensus string from the input data.
   1. Exhaustive Search (p109)
   2. Exhaustive Search with bound(p111)
   3. Exhaustive Search for median string search (p113)
   4. Exhaustive Search for median string search with prefix bound (p114)
   5. Exhaustive Search for median string search with prefix and suffix bound (ch4 slide p76~80)
   6. Greedy algorithm (p136)
   7. Simple CONSENSUS (described in the course)
   8. Your algorithm (from surveyed paper or from your brain)
2. For each argorithm, your program should generate the following results:
   • the consensus string and TotalDistance value
   • the spent time
   • Your programm should report the progress and estimated complete time while running.
3. You need to write a report, including the following items:
   • Describe your proposed algorithm and analysis it
   • time comparision of these eight algorithms by your testing (You should use a large size data for testing to show the differences.)
• Due

All stuff of this project, (runnable programs, packed source code files and your report) must send to TA before 4/17 5PM.

An example for input data

n=20 t=5 l=4
AGCCCCTGTGTAAGTTGCAT
TAAGAGCCCCTGTGTTGCAT
AGCCCCTTTGGTGTAAGCAT
CTGTGTAAGTTGAGCCCCAT
AGCCCCTAGTTGCGTGTAAT