Problem 797. Genome Sequence 003R: Sequence DNA of random positioned and flipped segments

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>This is Challenge 003R in the series on Genome DNA Sequencing. Challenge 3R includes flipped segments.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Genome\"><w:r><w:t>DNA Sequencing</w:t></w:r></w:hyperlink><w:r><w:t> is naively simplified into Cody Challenges.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Genome_sequence\"><w:r><w:t>Genome sizes</w:t></w:r></w:hyperlink><w:r><w:t> is another interesting wiki page.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>DNA is represented by symbols ACGT, which for Matlab will be encoded as 0123. The basic goal is to reconstruct the original serial string of ACGT given multiple short segments.</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>Example:</w:t></w:r><w:r><w:t> Genome = ACGTCGGCCATGGACATTACG</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given three overlapping pieces, ACGTCGGCCA, GCCATGGACATC, and GACATTACG these can be readily seen to overlap and create the original if the middle is recognized as being reversed with asymetric overlaps to its adjacent segments.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ACGTCGGCCATGGACATTACG\nACGTCGGCCAsssssssssss\nssssGCCATGGACATCsssss Middle Rev\nssssCTACAGGTACCGsssss Middle flipped\nssssssssssssGACATTACG]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Genome_003R Challenge is to reconstruct a genome under near ideal error free segment creation conditions. Segments may be reversed. The segments start at random locations.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Segments may be reversed (Change from 003)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Segments start at random positions</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Genome length is unconstrained</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Length of each segment - 48</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>All segments may overlap by 16 to 47 characters</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>No errors in the segments</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Genome is random (No duplicate starts or ends for 16 symbols of segments)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Segment order is scrambled</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> segs, Array of M rows of 48 value segments. Values are [0, 1, 2, 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>Output:</w:t></w:r><w:r><w:t> Gout, Genome vector of values [0,1,2,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>Example:</w:t></w:r><w:r><w:t> [0 1 2 3 2;1 1 2 2 3 2 ; 2 2 1 1 2] creates [0 1 2 3 2 2 1 1 2] W=5, Overlap=varies, Reverses may occur</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>Future:</w:t></w:r><w:r><w:t> Flipped segments(002), Random Position of Segment start locations(003),Random Segment Positions with Flips (003R), Parrot Sequence with Gen3 Long Segments, Extra Segments, Phage Phi X174, Parallel Processing Simulation(Shot Gun Approach), Haemophilus Influenza, Sequence with Segment Errors, and Chromosome 20 with its 59M length using 100K 4K-segments</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>"}]}

This is Challenge 003R in the series on Genome DNA Sequencing. Challenge 3R includes flipped segments. <a href="http://en.wikipedia.org/wiki/Genome">DNA Sequencing</a> is naively simplified into Cody Challenges. <a href="http://en.wikipedia.org/wiki/Genome_sequence">Genome sizes</a> is another interesting wiki page.DNA is represented by symbols ACGT, which for Matlab will be encoded as 0123. The basic goal is to reconstruct the original serial string of ACGT given multiple short segments.Example: Genome = ACGTCGGCCATGGACATTACGGiven three overlapping pieces, ACGTCGGCCA, GCCATGGACATC, and GACATTACG these can be readily seen to overlap and create the original if the middle is recognized as being reversed with asymetric overlaps to its adjacent segments.<pre class="language-matlab">ACGTCGGCCATGGACATTACG
ACGTCGGCCAsssssssssss
ssssGCCATGGACATCsssss Middle Rev
ssssCTACAGGTACCGsssss Middle flipped
ssssssssssssGACATTACG
</pre>Genome_003R Challenge is to reconstruct a genome under near ideal error free segment creation conditions. Segments may be reversed. The segments start at random locations.<ol><li>Segments may be reversed (Change from 003)</li><li>Segments start at random positions</li><li>Genome length is unconstrained</li><li>Length of each segment - 48</li><li>All segments may overlap by 16 to 47 characters</li><li>No errors in the segments</li><li>Genome is random (No duplicate starts or ends for 16 symbols of segments)</li><li>Segment order is scrambled</li></ol>Input: segs, Array of M rows of 48 value segments. Values are [0, 1, 2, 3].Output: Gout, Genome vector of values [0,1,2,3]Example: [0 1 2 3 2;1 1 2 2 3 2 ; 2 2 1 1 2] creates [0 1 2 3 2 2 1 1 2] W=5, Overlap=varies, Reverses may occurFuture: Flipped segments(002), Random Position of Segment start locations(003),Random Segment Positions with Flips (003R), Parrot Sequence with Gen3 Long Segments, Extra Segments, Phage Phi X174, Parallel Processing Simulation(Shot Gun Approach), Haemophilus Influenza, Sequence with Segment Errors, and Chromosome 20 with its 59M length using 100K 4K-segments

Solve

Solution Stats

4 Solutions
1 Solvers

Last Solution submitted on Apr 18, 2019

Last 200 Solutions

Problem Recent Solvers1

Problem Tags

dna flips genome hamming linking parfor random

Community Treasure Hunt

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

Start Hunting!

Problem 797. Genome Sequence 003R: Sequence DNA of random positioned and flipped segments

Solution Stats

Last 200 Solutions

Problem Recent Solvers1

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Problem 797. Genome Sequence 003R: Sequence DNA of random positioned and flipped segments

Solution Stats

Last 200 Solutions

Problem Recent Solvers1

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Players