Dynamic programming

3 problems from Rosalind — Bioinformatics Stronghold. Press Run on any block to execute it in your browser.

LGIS — Longest Increasing Subsequence

Longest increasing subsequence, which in a genomic setting is how conserved order is recovered from a comparison of two genomes: positions that stay in ascending order form a synteny block, and the rest is rearrangement.

LCSQ — Finding a Shared Spliced Motif

solved Problem statement

Any longest common subsequence is a valid answer, so the assertion checks the length and that the motif really is a subsequence of both strings.

SCSP — Interleaving Two Motifs

solved Problem statement

Any shortest common supersequence is valid, so the assertion checks the length and that both inputs are subsequences of the result.