Connection Status:
Competition Arena > DNADeletion

DNADeletion

SRM 435 · 2009-02-12 · by almelv

SRM 435 · 2009-02-12 · by almelv · Dynamic Programming, Simulation
Class Name: DNADeletion
Return Type: int
Method Name: differentProteins
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

In genetics, a DNA sequence is a sequence of nucleotides (A, C, G or T). Some DNA sequences translate to proteins, which are non-empty sequences of amino acids. Let's examine the DNA translation process::
  1. From left to right, split the DNA sequence into consecutive, non-overlapping triples of nucleotides. Each triple is called a codon. There may be one or two nucleotides left over at the end - those should be ignored. For example, the DNA sequence "ACCTGTACG" will produce the codon sequence "ACC", "TGT", "ACG". The DNA sequence "ACCTGTAC" will produce the codon sequence "ACC", "TGT" ("AC" is left over and ignored).
  2. You are given a codon table that maps codons to their associated amino acids. From left to right, look up each codon in the sequence generated above and replace it with its associated amino acid. Every codon in the sequence must have an associated amino acid - otherwise, the DNA sequence does not translate to a protein. For example, if "ACC" and "ACG" each map to threonin ("thr") and "TGT" maps to cysteine ("cys"), the DNA sequence "ACCTGTACG" will translate to the protein "thr cys thr".
Sometimes, after replication, one or more nucleotides in a DNA sequence go missing. This situation is called deletion. After a deletion, a DNA sequence can become any of its subsequences. For example, "ACTG" may become "ACG" or "CG".

You are given a String[] DNASequence containing a DNA sequence. Concatenate the elements of DNASequence to obtain the DNA sequence. You are also given a String[] codonTable containing the codon table. Each element is formatted "CODON AMINOACID" (quotes for clarity), where AMINOACID is the name of the amino acid associated with codon CODON. Compute the number of different possible proteins that the given DNA sequence can translate to after undergoing zero or more deletions. Since this number can be quite large, return its value modulo 1000000007. Remember that only nonempty amino acid sequences are considered proteins.

Constraints

  • DNASequence will contain between 1 and 50 elements, inclusive.
  • Every element of DNASequence will contain between 1 and 50 characters, inclusive.
  • Every element of DNASequence will contain only characters 'A', 'C', 'T', 'G'.
  • codonTable will contain between 1 and 50 elements, inclusive.
  • Every element of codonTable will contain a codon, followed by a single space, followed by an amino acid.
  • Every codon in codonTable will contain exactly 3 characters.
  • Every codon in codonTable will contain only characters 'A', 'C', 'T', 'G'.
  • Every codon in codonTable will be unique.
  • Every amino acid in codonTable will contain between 1 and 20 characters.
  • Every amino acid in codonTable will contain only letters ('a'-'z', 'A'-'Z').
Examples
0)
{"ACTG"}
{"ACT gua", "ACG cys", "ATG leu", "CTG thr"}
Returns: 4

You can get proteins: "gua" (deletion of 'G' or no deletion), "cys" (deletion of 'T'), "leu" (deletion of 'C'), "thr" (deletion of 'A'). Other deletions do not result in proteins.

1)
{"AAACCC"}
{"AAA thr", "CCC cys"}
Returns: 3

You can get proteins: "thr", "cys" and "thr cys".

2)
{"AAATCCC"}
{"AAA gua","TCC dop","AAT dop","CCC gua"}
Returns: 5

You can get proteins: "gua", "dop", "gua dop" (from sequence "AAATCC"), "dop gua" (from sequence "AATCCC"), "gua gua" (from sequence "AAACCC").

3)
{"TACAGC"}
{"TCA rvykZ","GTA jYAv","ATG rvykZ","TTT jYAv","CTG rvykZ","ACT jYAv"}
Returns: 1
4)
{"TATCC"}
{"GAA s","ATG s","ACA S","CTC V","GGG YScV"}
Returns: 0
81)
{"ATGCGCATTAACCTCCTACCATGGAAGGGACGTAACCCGGCAATTTGATC",
 "CTGATGACGGCATAAGCTACCCCTAGAGGTAAAAATGCATACTGCGTGCT",
 "ATGCAG"}
{"AAC RpjZt","AAT ZeiC","GCA ChZwh","TCC RpjZt","GAA I",
 "TAG ZeiC","CTG dVK","GAG ZeiC","GTG I","AAG q","ATT dVK",
 "AGA cJEjM","GGG KONUd","GTC ZRV","GGC ZeiC","TTA KONUd",
 "GAC q","CCA q","GCC ZRV","GCG RpjZt","CCT ZRV","ATG dVK",
 "ATC ChZwh","CTC cJEjM","CCC q","ATA dWjz","TTG DkEG",
 "CAG q","CAA ZRV","ACT dVK","TCG dVK","ACC I","CGC dVK"}
Returns: 455985264

Be sure to concatenate the elements of DNASequence.

Submissions are judged against all 109 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DNADeletion with a public method int differentProteins(vector<string> DNASequence, vector<string> codonTable) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous