Problem 79. DNA N-Gram Distribution

Created by Cody Team

Solve Later

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.

So for

 s = 'AACTGAACG'

and

 n = 3

we get the following n-grams (trigrams):

 AAC, ACT, CTG, TGA, GAA, AAC, ACG

Since AAC appears twice, then the answer, hifreq, is AAC. There will always be exactly one highest frequency n-gram.

This problem was originally inspired by a MATLAB Newsgroup discussion.

Solve

Solution Stats

1041 Solutions
411 Solvers

Last Solution submitted on Feb 18, 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 Solvers411

Problem Tags

matlab

Problem 79. DNA N-Gram Distribution

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers411

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 Solvers411

Suggested Problems

More from this Author95

Problem Tags

Players