Category Archives: Biology

Finding a Motif in DNA

Posted by on May 14, 2013 No comments | 5 views 
Problem
Given two strings s and t, t is a substring of s if t is contained as a contiguous collection of symbols in s (as a result, t must be no longer than s).

The position of a symbol in a string is the total number of symbols found to its left, including itself (e.g., the positions of all occurrences of 'U' in "AUGCUUCAGAAAGGUCUUACG" are 2, 5, 6, 15, 17, and 18). The symbol at position i of s is denoted by s[i].

A substring of s can be represented as s[j:k], where j and k represent the starting and ending positions of the substring in s; for example, if s = "AUGCUUCAGAAAGGUCUUACG", then s[2:5] = "UGCU".

The location of a substring s[j:k] is its beginning position j; note that t will have multiple locations in s if it occurs more than once as a substring of s (see the Sample below).

Given: Two DNA strings s and t (each of length at most 1 kbp).

Return: All locations of t as a substring of s.

Sample Dataset
GATATATGCATATACTT
ATAT

Sample Output
2 4 10

This problem requires locating the positions of the substring. I use sliding windows to locate all the possible positions.
Read more »

Mendel's First Law

Posted by on April 15, 2013 No comments | 37 views 
Problem
Probability is the mathematical study of randomly occurring phenomena. We will model such a phenomenon with a random variable, which is simply a variable that can take a number of different distinct outcomes depending on the result of an underlying random process.

For example, say that we have a bag containing 3 red balls and 2 blue balls. If we let X represent the random variable corresponding to the color of a drawn ball, then the probability of each of the two outcomes is given by Pr(X=red)=3/5 and Pr(X=blue)=2/5.

Random variables can be combined to yield new random variables. Returning to the ball example, let Y model the color of a second ball drawn from the bag (without replacing the first ball). The probability of Y being red depends on whether the first ball was red or blue. To represent all outcomes of X and Y, we therefore use a probability tree diagram. This branching diagram represents all possible individual probabilities for X and Y, with outcomes at the endpoints ("leaves") of the tree. The probability of any outcome is given by the product of probabilities along the path from the beginning of the tree; see Figure 2 for an illustrative example.


Figure 2.

An event is simply a collection of outcomes. Because outcomes are distinct, the probability of an event can be written as the sum of the probabilities of its constituent outcomes. For our colored ball example, let A be the event "Y is blue." Pr(A) is equal to the sum of the probabilities of two different outcomes: Pr(X=blue and Y=blue)+Pr(X=red and Y=blue), or 3/10+1/10=2/5 (see Figure 2 above).

Given: Three positive integers k, m, and n, representing a population containing k+m+n organisms: k individuals are homozygous dominant for a factor, m are heterozygous, and n are homozygous recessive.

Return: The probability that two randomly selected mating organisms will produce an individual possessing a dominant allele (and thus displaying the dominant phenotype). Assume that any two organisms can mate.

Sample Dataset
2 2 2

Sample Output
0.78333

This problem requires calculating the compound probability, which is equal to the probability of the first event multiplied by the probability of the second event.

The first even is select two organisms randomly from the population, and its probability can be calculated as illustrated in Figure 2.

The second even is the genetic recombination between the selected organisms, and its probability can be determined by Mendel’s First Law.

The final answer is the total sum of these compound probabilities.

Read more »

Rabbits and Recurrence Relations

Posted by on April 2, 2013 No comments | 45 views 
Problem
A sequence is an ordered collection of objects (usually numbers), which are allowed to repeat. Sequences can be finite or infinite. Two examples are the finite sequence (Π,−√2,0,Π) and the infinite sequence of odd numbers (1,3,5,7,9,…). We use the notation an to represent the n-th term of a sequence.

A recurrence relation is a way of defining the terms of a sequence with respect to the values of previous terms. In the case of Fibonacci's rabbits from the introduction, any given month will contain the rabbits that were alive the previous month, plus any new offspring. A key observation is that the number of offspring in any month is equal to the number of rabbits that were alive two months prior. As a result, if Fn represents the number of rabbit pairs alive after the n-th month, then we obtain the Fibonacci sequence having terms Fn that are defined by the recurrence relation Fn=Fn-1+Fn-2 (with F1=F2=1 to initiate the sequence). Although the sequence bears Fibonacci's name, it was known to Indian mathematicians over two millennia ago.

When finding the n-th term of a sequence defined by a recurrence relation, we can simply use the recurrence relation to generate terms for progressively larger values of n. This problem introduces us to the computational technique of dynamic programming, which successively builds up solutions by using the answers to smaller cases.

Given: Positive integers n≤40 and k≤5.

Return: The total number of rabbit pairs that will be present after n months if each pair of reproduction-age rabbits produces a litter of k rabbit pairs in each generation (instead of only 1 pair).

Sample Dataset
5 3

Sample Output
19

It is very intuitive to implement Fibonacci sequence using recursive algorithm. But it's performance is poor with O(2n). This problem requires using dynamic programming, which caches answers to smaller cases that were calculated previous, to optimize performance.

I have presented an R version of Fibonacci, which employ a local global vector to cache the previous results. In C, I use a static variable to do the same thing. Actually this program is translated from the R implementation.

NOTE: unsigned long int was used to store Fibonacci numbers, since they increase quite fast.

Read more »

Calculating Protein Mass

Posted by on March 26, 2013 No comments | 24 views 
Problem
In a weighted alphabet, every symbol is assigned a positive real number called a weight. A string formed from a weighted alphabet is called a weighted string, and its weight is equal to the sum of the weights of its symbols.

The standard weight assigned to each member of the 20-symbol amino acid alphabet is the monoisotopic mass of the corresponding amino acid.

Given: A protein string P of length at most 1000 aa.

Return: The total weight of P. 

Sample Dataset
SKADYEK

Sample Output
821.392

This problem, likes most of the previous problems, is actually a mapping problem. Instead of converting one alphabet to the other, it requires mapping to a positive real number.

The function getAAMass was implemented to work as a hash table, which return weight (value) from alphabet (key) inquiry.
Read more »

Protein Translation

Posted by on March 18, 2013 No comments | 22 views 
Problem
The 20 commonly occurring amino acids are abbreviated by using 20 letters from the English alphabet (all letters except for B, J, O, U, X, and Z). Protein strings are constructed from these 20 symbols. Henceforth, the term genetic string will incorporate protein strings along with DNA strings and RNA strings.

The RNA codon table dictates the details regarding the encoding of specific codons into the amino acid alphabet.

Given: An RNA string s corresponding to a strand of mRNA (of length at most 10 kbp).

Return: The protein string encoded by s.

Sample Dataset
AUGGCCAUGGCGCCCAGAACUGAGAUCAAUAGUACCCGUAUUAACGGGUGA

Sample Output
MAMAPRTEINSTRING

Based on the central dogma of molecular biology, protein is created from RNA, which in turn is created from DNA. The genetic code describes the details of how information of amino acid order of a protein is stored in the nucleic acid sequence of DNA.

This is actually a mapping problem. We can translate a DNA sequence by reading each of its codon (should start from start codon) until the stop codon, and mapping the codon to its corresponding encoded amino acid.

Here, I defined a structure call codon to store each codon (3bp) and its encoded amino acid. Actually, in computer memory the structure of codon is an array of length 4. This is why strncmp function was used here other than strcmp. It maybe weird, but I think using structure is more human readable.

Read more »