Six-Frame ORF Finder

Intermediate Bioinformatics ORF Translation Reading Frames Gene Prediction
Significance:

Before annotation tools existed, finding genes meant scanning all six reading frames —
three on each strand — for stretches bounded by a start codon and a stop codon. Six-frame ORF finding
is still the first step in annotating any newly sequenced contig, and it forces you to hold two ideas
at once: that DNA is double-stranded, and that the same sequence encodes completely different proteins
depending on where you start reading.

Statement

Given a DNA sequence, find every distinct protein string that can be translated from an
open reading frame in any of the six reading frames (three forward, three on the reverse complement).

An ORF starts at an ATG codon, proceeds in steps of three, and ends at the first in-frame stop codon
(TAA, TAG, or TGA). The stop codon is not translated. An ORF that runs off the end of the sequence
without hitting a stop codon is not reported.

Print each distinct protein string on its own line, sorted in ascending lexicographic order. If no ORF
is found, print nothing.

Input — read from standard input
Variable Type Description
dna
line 1
 str The DNA sequence to scan
3 <= len(dna) <= 1000, uppercase A, C, G, T only

These variables are already read for you in the starter code on the right.

Output

str distinct protein strings, one per line, sorted ascending lexicographically

Sample Cases
Sample 1
Input
AGCCATGTAGCTAACTCAGGTTACATGGGGATGACCCCGCGACTTGGATTAGAGTCTCTTTTGGAATAAGCCTGAATGATCCGAGTAGCATCTCAG
Expected Output
M
MGMTPRLGLESLLE
MLLGSFRLIPKETLIQVAGSSPCNLS
MTPRLGLESLLE
Four distinct proteins are recoverable across the six frames of this sequence.
Sample 2
Input
ATGTAA
Expected Output
M
A minimal ORF: start codon immediately followed by a stop, giving the empty protein.

Submit also runs your code against 5 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.

Constraints
  • 3 <= length(dna) <= 1000
  • Both strands must be searched: the forward sequence and its reverse complement
  • Duplicate protein strings arising from different frames are reported only once
  • Output is sorted lexicographically to make grading deterministic
Further Reading
  • Build the reverse complement once, then run the same scanning routine over both strings.
  • For each strand, try offsets 0, 1 and 2 as the frame start.
  • Collect results in a set to deduplicate, then sort before printing.
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...
Expected: dna (str)
Next Problem
FASTQ Quality Control