Suggested problems

Hydropathy index

Dec. 30, 2012, 6:25 p.m. by Wouter Saelens

Biological Motivation

An important characteristic of biological membranes is that they are semi-permeabel, i.e. they let some molecules through and some not. This semi-permeability is created because the membrane itself is mainly hydrophobic, while the outside membrane, with its major component water, is hydrophilic. Integral membrane proteins are proteins embedded in the membrane. These proteins have transmembrane domains who pass through the membrane and are enriched in hydrophobic amino acids like tryptophane while being depleted in hydrophilic amino acids like glutamate.

Problem

A hydropathy scale contains a hydropathy index for each of the 20 standard amino acids. The hydropathy index of a sequence is the average of the hydropathy indices of each residu. A commonly used hydropathy scale is the Kyle-Doolittle scale.

Given: A protein string $s$ of length $n$ ($n≤1000$), $l$ ($l<n$) and $k$.

Return: All substrings of $s$ of length $l$ having a hydropathy index higher than $k$. Substrings can overlap. Use the Kyle-Doolittle scale.

Sample Dataset

LMDENANVVCKGRFFFCGWFMQVEEFWQMVQFYIDVIFIY
4 1.175

Sample Output

ANVV
NVVC
VVCK
FFFC
FFCG
FMQV
MVQF
IDVI
DVIF
VIFI
IFIY