Part 1

1) When attempting to predict the 3-dimensional structure of a protein from its amino acid sequence, a good sequence alignment can allow one to predict structure homology. If a good alignment exists with a sequence whose protein structure has already been discovered, then it is often reasonable to predict the structure of the new protein to be similar.

2) For in vitro evolution experiments, it is important for the researcher to be able to be able to compare the mutations that are generated versus the original sequence. Here, sequence alignment allows them to correlate the end expression changes with changes in nucleotide sequence.

3) In horizontal gene transfer events, the gene recipient will presumably have a gene matching one from the gene "donor". By using sequence alignment, such matching genes between two separate genomes can be identified to rapidly locate potential horizontal gene transfers.

4) Sequence alignment can aid in the identification of regulatory elements such as riboswitches by attmepting to align known regulatory elements against the genome of interest. Matches with good identity scores are likeley to be good candidates as regulatory elements.

Part 2

Attached are the program nussinov.pl implementing the Nussinov algorithm, as well as the plot of run-times for varying sequence lengths.

My particular program takes the RNA sequence input from standard input.

The time complexity observed was very consistent with the expected complexity of the algorithm (O(L^3)).