Problem 79. DNA N-Gram Distribution

Created by Cody Team

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given a string s and a number n, find the most frequently occurring n-gram in the string, where the n-grams can begin at any point in the string. This comes up in DNA analysis, where the 3-base reading frame for a codon can begin at any point in the sequence.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So for</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s = 'AACTGAACG']]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ n = 3]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>we get the following n-grams (trigrams):</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ AAC, ACT, CTG, TGA, GAA, AAC, ACG]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Since AAC appears twice, then the answer, hifreq, is AAC. There will always be exactly one highest frequency n-gram.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>This problem was originally inspired by a</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/newsreader/view_thread/278173\"><w:r><w:rPr><w:i/></w:rPr><w:t>MATLAB Newsgroup discussion</w:t></w:r></w:hyperlink><w:r><w:rPr><w:i/></w:rPr><w:t>.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

1243 Solutions
614 Solvers

Last Solution submitted on Aug 12, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

E Chang on 22 Oct 2018

It should be noted that spaces should be ignored or else test suites 3 and 5 fail.

Solution Comments

Solution 407580

1 Comment

1 Comment

Ramoflaple on 28 Jul 2015

good use of 'hankel' function

Solution 341253

1 Comment

1 Comment

danteliujie on 23 Apr 2019

cool solution

Solution 210138

2 Comments

2 Comments

Claudio Gelmi on 28 Feb 2013

Sorry about this, but I got stuck and I want to learn how to do it. After looking at several solutions, I found my mistake and was able to create my own solution :)

Yao-Siang Su on 8 Dec 2013

What happens if the test suite changed in the future?

Solution 126262

1 Comment

1 Comment

Gwendolyn Fischer on 11 Dec 2012

This solution is not correct in general, as the way of using hankel here, generates n-1 fake fragments

Solution 59734

1 Comment

1 Comment

Peter Wittenberg on 31 Mar 2012

Clever usage of the Hankel matrix. I don't automatically think of the Hankel for this application, but it really works well. Thanks - I've learned something

Solution 13269

1 Comment

1 Comment

David Young on 2 Feb 2012

What's the point of a 'solution' like this? It passes the test suite, but in what way was it interesting for you to write it?

Problem Recent Solvers614

Problem Tags

matlab

Problem 79. DNA N-Gram Distribution

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers614

Suggested Problems

More from this Author95

Problem Tags

Problem 79. DNA N-Gram Distribution

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers614

Suggested Problems

More from this Author95

Problem Tags

Players