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

1501 Solutions
703 Solvers

Last Solution submitted on Dec 07, 2021

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 Solvers703

Problem Tags

matlab

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 79. DNA N-Gram Distribution

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers703

Suggested Problems

More from this Author95

Problem Tags

Community Treasure Hunt

Problem 79. DNA N-Gram Distribution

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers703

Suggested Problems

More from this Author95

Problem Tags

Community Treasure Hunt

Players