Mastering Python for Bioinformatics

Chapter 17. DNA Synthesizer: Creating Synthetic Data with Markov Chains

A Markov chain is a model for representing a sequence of possibilities found in a given dataset. It is a machine learning (ML) algorithm because it discovers or learns patterns from input data. In this exercise, I’ll show how to use Markov chains trained on a set of DNA sequences to generate novel DNA sequences.

In this exercise, you will:

• Read some number of input sequence files to find all the unique k-mers for a given k.

• Create a Markov chain using these k-mers to produce some number of novel sequences of lengths bounded by a minimum and maximum.

• Learn about generators.

• Use a random seed to replicate random selections.

Understanding Markov Chains

In Claude Shannon’s “A Mathematical Theory of Communication” (1948), the author describes a Markoff process that is surprisingly similar to graphs and the finite state diagrams I’ve been using to illustrate regular expressions. Shannon describes this process as “a finite number of possible states of a system” and “a set of transition probabilities” that one state will lead to another.

For one example of a Markov process, Shannon describes a system for generating strings of text by randomly selecting from the 26 letters of the English alphabet and a space. In a “zero-order approximation,” each character has an equal probability of being chosen. This process generates strings where letter combinations like bz and qr might appear as ...