Friday, April 11, 2008


As you know, the DNA that guides the development of all living things is just a very long string where each character is one of the four letters: A, G, C, T. Implement a class called DNAString which stores as its member variable one such string, can turn itself into a string, and implements a function called positionOf which takes as input a string and returns the starting position of that substring in the DNA string.

For the positionOf we search from left to right. The inner break means we don't waste time on impossible matches.

public class DNAString {

/** The gene. I choose to represent it as an array since its is then
more natural to access random positions and I can change it in
place without copying the whole thing (Remember: Strings are
immutable). */

protected char[] strand;

public DNAString(int length){
strand= new char[length];

public void set(String g){
for (int i=0; i < g.length(); i++){
strand[i] = g.charAt(i);

public String toString(){
String result = "";
for (char g : strand){
result += g;
return result;

/** @param s the substring we are looking for.
Returns the starting position of s in this DNAString or -1 if s is
not found anywhere in this strand */

public int positionOf(String s){
for (int i=0; i < strand.length - s.length(); i++){
boolean match = true;
for (int j =0; j< s.length(); j++){
if (strand[i+j] != s.charAt(j)) {
match = false;
if (match) {
return i;
return -1;

public static void main (String [] args){
DNAString joe = new DNAString(joeDNA.length());

System.out.println("AAGT is first found at position " + joe.positionOf("AAGT"));


No comments: