Problem

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Example

given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", return: ["AAAAACCCCC", "CCCCCAAAAA"].

JavaScript Code

function findRepeatedDnaSequences(s) {
    var result = [];
 
    var len = s.length;
    if (len < 10) {
        return result;
    }
 
    var map = {};
    map['A'] = 0;
    map['C'] = 1;
    map['G'] = 2;
    map['T'] = 3;
 
    var temp = [];
    var added = [];
 
    var hash = 0;
    for (var i = 0; i < len; i++) {
        if (i < 9) {
            //each ACGT fit 2 bits, so left shift 2
            hash = (hash << 2) + map[s.charAt(i)]; 
        } else {
            hash = (hash << 2) + map[s.charAt(i)];
            //make length of hash to be 20
            hash = hash &  (1 << 20) - 1; 
 
            if (temp.indexOf(hash)!=-1 && added.indexOf(hash)==-1) {
                result.push(s.substring(i - 9, i + 1));
                added.push(hash); //track added
            } else {
                temp.push(hash);
            }
        }
 
    }
 
    return result;
}

console.log(findRepeatedDnaSequences('AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT'));

3 comments:

  1. 1,3,6,8-tetra(pyridin-4-yl)pyrene - Alfa Chemistry offers an extensive catalog of materials in a wide range of applications. Products listed on our website are either in stock or can be resynthesized within a reasonable time frame. In stock products can be shipped out within 3-5 business days upon receipt of customers' purchase order.

    ReplyDelete
  2. Metal Organic Framework - Alfa Chemistry offers an extensive catalog of nanomaterials in a wide range of applications. Products listed on our website are either in stock or can be resynthesized within a reasonable time frame. In stock products can be shipped out within 3-5 business days upon receipt of customers' purchase order.

    ReplyDelete

Blogroll

Popular Posts