Rosalind - Open Reading Frames

Aug 20, 2020 rosalind

Problem:

Please find the problem here.

Solution:

There are two parts to this problem. We need to find all the start and stop codons, and we need to pair them up so that we know where to start and stop decoding.

The former is performed using the Aho Corasick algorithm, by using a trie, we can match all codons in a single pass.

Imagine we are walking from left to right, whenever we see a stop codon, we want all the start codon before it that is after the last stop codon. That structure perfectly mirror a stack, that is what I used.

Code: