Download chromosome 6 From Human Genome Resources at NCBI, select link GRCh38, Fasta.
Extract entry NC_000006.12 Homo sapiens chromosome 6, GRCh38.p13 Primary Assembly.
Extract bases [100,000–1,099,999]; starting with ttggtaccat and ending in TAATTGCAGT. Denote this as S. (標作S).
For simplicity map all letters to lower case; i.e. A-->a, C-->c, etc.
Write a program (in C or whatever) implementing (plain) Markov models of order 0,1 and 2; for generating DNA sequences. Fit the parameters of these three models to S and compute the log base 2 probability of each of them generating S (given that they generate a sequence of that length).
Write a program (in C or whatever) implementing a hidden Markov model to generate sequences.
Because this is an exercise for learning, please implement the models yourself (do not use any software packages for Markov or hidden Markov models).
Compute the log base 2 probability of your model generating S (given that it generates some sequence that length).
You may hand tune your parameters or use a learning algorithm (extra credit for implementing Baum-Welch or similar learning algorithm yourself), to make the probability of S as large as possible; however you may not use more than 100 free parameters (for comparison a 1st order Markov model has 16 parameters (P[x|y] for x,y ∈ {a,c,g,t}, but 4 "sum-to-one" constraints, yielding 12 free parameters.
See if your parameters can be tuned to give a higher probability than the plain Markov models.
To keep the models general, models are not allowed to emit more than 3 bases in one step (in particular the model cannot simply emit S in one step!).
Compute the most likely state sequence that the model would traverse when emitting S.
After designing your model and fitting its parameters to S; compute the probabilities that they would generate:
Write your names in the project readme. Please just give us your source files, no need to check in data files or executables (我不要你的.exe檔).