Problem 939. DNA Pattern Match: Performance Metric - Speed

Created by Richard Zapor

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>The Challenge is to Rapidly find matches of DNA sequences, Length=6, in a 1,800,000 long DNA file.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>At</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://imacst.com/issues/volume-3issue-1/\"><w:r><w:t>IMACST</w:t></w:r></w:hyperlink><w:r><w:t> the paper</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://imacst.com/web_documents/1202002.pdf\"><w:r><w:t>An Intelligent and Efficient Matching Algorithm to Finding a DNA Pattern</w:t></w:r></w:hyperlink><w:r><w:t> claimed an astounding time improvement from 9.94 seconds to 7.84 seconds, 21% time reduction, to match six segments of length 6 in a 1.8M long DNA file. Basic probability asserts 1.8M/4^6 * 6 = 2637 matches. The paper's test case produced 2346 matches. The method employed used text processing in C++. The paper's L=25 and L=50 cases will be later challenges.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Matlab can achieve matching a six pattern set of L=6 in &lt;15 msec (i5/16GB). This is merely a 99.8% time reduction.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Challenge Description:</w:t></w:r><w:r><w:t> DNA is made of letters ACGT,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/DNA\"><w:r><w:t>wiki DNA</w:t></w:r></w:hyperlink><w:r><w:t>, which for the purposes of this Matlab Cody Challenge are given values 0 thru 3. (ACGT= 0123)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [DNA, DNA_ID, Patterns]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>DNA is a 1.8M long uint8 row vector of values 0 thru 3.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>DNA_ID identifies the DNA segment being processed. Multiple calls using the same DNA_ID will be performed. The first call of a DNA_ID is not timed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Patterns is an Nx6 uint8 array where each row corresponds to a search pattern.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> Locations</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Locations of all start indices that match any of the patterns</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring:</w:t></w:r><w:r><w:t> Average Time (msec) for a block of L=6 patterns</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>DNA= [0 1 2 3 3 2 1 0 1 2 3 3]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Pattern = [2 3 3 2 1 0]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Locations = [3]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Hints:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Vectorization (Base 4 to Base 10 of 6 character words)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Bitshift/Reshape to create all words</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Logical Indexing</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Coming soon: Genome DNA sequencing of PhagePhix174 and Haempphilus Influenza</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>"}]}

The Challenge is to Rapidly find matches of DNA sequences, Length=6, in a 1,800,000 long DNA file.At <a href="http://imacst.com/issues/volume-3issue-1/">IMACST</a> the paper <a href="http://imacst.com/web_documents/1202002.pdf">An Intelligent and Efficient Matching Algorithm to Finding a DNA Pattern</a> claimed an astounding time improvement from 9.94 seconds to 7.84 seconds, 21% time reduction, to match six segments of length 6 in a 1.8M long DNA file. Basic probability asserts 1.8M/4^6 * 6 = 2637 matches. The paper's test case produced 2346 matches. The method employed used text processing in C++. The paper's L=25 and L=50 cases will be later challenges.Matlab can achieve matching a six pattern set of L=6 in &lt;15 msec (i5/16GB). This is merely a 99.8% time reduction.Challenge Description:
DNA is made of letters ACGT, <a href="http://en.wikipedia.org/wiki/DNA">wiki DNA</a>, which for the purposes of this Matlab Cody Challenge are given values 0 thru 3. (ACGT= 0123)Input: [DNA, DNA_ID, Patterns]<ul><li>DNA is a 1.8M long uint8 row vector of values 0 thru 3.</li><li>DNA_ID identifies the DNA segment being processed. Multiple calls using the same DNA_ID will be performed. The first call of a DNA_ID is not timed.</li><li>Patterns is an Nx6 uint8 array where each row corresponds to a search pattern.</li></ul>Output: LocationsLocations of all start indices that match any of the patternsScoring: Average Time (msec) for a block of L=6 patternsExample:<ul><li>DNA= [0 1 2 3 3 2 1 0 1 2 3 3]</li><li>Pattern = [2 3 3 2 1 0]</li><li>Locations = [3]</li></ul>Hints:<ul><li>Vectorization (Base 4 to Base 10 of 6 character words)</li><li>Bitshift/Reshape to create all words</li><li>Logical Indexing</li></ul>Coming soon: Genome DNA sequencing of PhagePhix174 and Haempphilus Influenza

Solve

Solution Stats

24 Solutions
8 Solvers

Last Solution submitted on Feb 20, 2019

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 939. DNA Pattern Match: Performance Metric - Speed

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Problem 939. DNA Pattern Match: Performance Metric - Speed

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Players