# Program1.py
#
# This program solves the first problem from Lab 3: finding candidate
# genes in a DNA sequence.  The DNA sequence is represented as uppercase
# letters ('A', 'C', 'T', 'G').  For the purposes of this program, a
# candidate gene is defined as a sequence of codons, beginning with a
# start codon (ATG) and ending with a stop codon (TAA, TAG, or TGA), whose
# length is at least 20 codons.  (In terms of nucleotides, the length
# must be at least 60 nucleotides.)
#
# The program uses, as its basis, the solution for the last problem from
# the previous lab, in which we found start codons (ATG).  When a start
# codon is found, we go looking for a stop codon and see if we have a
# candidate gene, then return to looking for start codons (and, thus,
# other candidate genes).
#
# Strategy:
#
#     for each codon starting at a position i (with i being between 0 and
#                                              three characters short of
#                                              the end of the sequence)
#     {
#         if the codon starting at position i is ATG
#         {
#             for each "on frame" codon starting at position j
#             (with j starting at i+3, i.e. just past the ATG,
#              and ending three characters short of the end of
#              the sequence)
#             {
#                 if the codon starting at position j is a stop codon
#                 {
#                     if the length of the sequence from ATG to the stop
#                     codon we found is at least 60 characters
#                     {
#                         this is a candidate gene; print information
#                         about it on the screen
#                     }
#
#                     whether the sequence was long enough or not, stop
#                     looking for a stop codon
#                 }
#             }
#         }
#    }


dnaSequence = "CCATGTTACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCTAATAC"

for i in range(0, len(dnaSequence)-2):
    if dnaSequence[i : i+3] == 'ATG':
        for j in range(i+3, len(dnaSequence)-2, 3):
            if dnaSequence[j : j+3] == 'TAA' or dnaSequence[j : j+3] == 'TAG' or dnaSequence[j : j+3] == 'TGA':
                if j+3-i >= 60:
                    print "-----"
                    print "Candidate gene found!"
                    print "     Start position    :", (i+1)
                    print "     Length (in codons):", (j+3-i)/3
                break