Problem 969. Genome Sequence 003: DNA Sequence with random positioned 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 Challenge series will evolve the complexity of Genome DNA Sequencing.</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> and the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Shotgun_sequencing\"><w:r><w:t>Shot Gun Method</w:t></w:r></w:hyperlink><w:r><w:t> will be 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. Segments are gleaned from multiple copies of the Virus/Bacteria/Chromosome thus there are overlapping, duplicative, and flipped segments. There are potential errors and duplicative stretches in the created segments. Chromosome 20 in its 59,187,298 base pairs has a segment of 820 that is repeated in at least two locations. The data being non-random largely increase lengths of duplicative stretches.</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,CTACAGGTACCG, and GACATTACG these can be readily seen to overlap and create the original if the middle is recognized as having asymetric overlaps with 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\nssssCTACAGGTACCGsssss Middle\nssssssssssssGACATTACG]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Genome_003 Challenge is to reconstruct a genome under near ideal error free segment creation conditions. No segments are 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 start at random positions (Genome_003 change from 001)</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 2 3 2 2; 2 2 1 1 2] creates [0 1 2 3 2 2 1 1 2] W=5, Overlap=varies</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), 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 Challenge series will evolve the complexity of Genome DNA Sequencing. <a href="http://en.wikipedia.org/wiki/Genome">DNA Sequencing</a> and the <a href="http://en.wikipedia.org/wiki/Shotgun_sequencing">Shot Gun Method</a> will be 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. Segments are gleaned from multiple copies of the Virus/Bacteria/Chromosome thus there are overlapping, duplicative, and flipped segments. There are potential errors and duplicative stretches in the created segments. Chromosome 20 in its 59,187,298 base pairs has a segment of 820 that is repeated in at least two locations. The data being non-random largely increase lengths of duplicative stretches.Example: Genome = ACGTCGGCCATGGACATTACGGiven three overlapping pieces, ACGTCGGCCA,CTACAGGTACCG, and GACATTACG these can be readily seen to overlap and create the original if the middle is recognized as having asymetric overlaps with its adjacent segments.<pre class="language-matlab">ACGTCGGCCATGGACATTACG
ACGTCGGCCAsssssssssss
ssssCTACAGGTACCGsssss Middle
ssssssssssssGACATTACG
</pre>Genome_003 Challenge is to reconstruct a genome under near ideal error free segment creation conditions. No segments are reversed. The segments start at random locations.<ol><li>Segments start at random positions (Genome_003 change from 001)</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 2 3 2 2; 2 2 1 1 2] creates [0 1 2 3 2 2 1 1 2] W=5, Overlap=variesFuture: Flipped segments(002), Random Position of Segment start locations(003), 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

9 Solutions
3 Solvers

Last Solution submitted on Sep 18, 2013

Last 200 Solutions

Problem Recent Solvers3

Problem Tags

Problem 969. Genome Sequence 003: DNA Sequence with random positioned segments

Solution Stats

Last 200 Solutions

Problem Recent Solvers3

Suggested Problems

More from this Author236

Problem Tags

Problem 969. Genome Sequence 003: DNA Sequence with random positioned segments

Solution Stats

Last 200 Solutions

Problem Recent Solvers3

Suggested Problems

More from this Author236

Problem Tags

Players