Problem 863. Genome Sequence 001: Introductory DNA Sequencing

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 and duplicative 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> G = 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, GGCCATGGACAT, and GACATTACG these can be readily seen to overlap and create the original.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ACGTCGGCCATGGACATTACG\nACGTCGGCCAsssssssssss\nsssssGGCCATGGACATssss\nssssssssssssGACATTACG]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Genome_001 Challenge is to reconstruct a genome under ideal segment creation conditions.</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>Segments begin at locations 1, 33, 65,...32N+1 (N=0:K, L_Genome=32K+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 are provided once (Essentially two copies of a genome were cut into pieces with overlaps)</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 read left to right (no flips)</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>Segments will be 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 2; 2 2 3 1; 3 1 1 2] creates [0 1 2 2 3 1 1 2] M=3,W=4, Overlap=2</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, Random Position of Segment start locations, 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 (Matlab - 19.2 sec single thread benchmark)</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 and duplicative 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: G = ACGTCGGCCATGGACATTACGGiven three overlapping pieces, ACGTCGGCCA, GGCCATGGACAT, and GACATTACG these can be readily seen to overlap and create the original.<pre class="language-matlab">ACGTCGGCCATGGACATTACG
ACGTCGGCCAsssssssssss
sssssGGCCATGGACATssss
ssssssssssssGACATTACG
</pre>Genome_001 Challenge is to reconstruct a genome under ideal segment creation conditions.<ol><li>Length of each segment - 48</li><li>Segments begin at locations 1, 33, 65,...32N+1 (N=0:K, L_Genome=32K+48)</li><li>All segments are provided once (Essentially two copies of a genome were cut into pieces with overlaps)</li><li>Segments read left to right (no flips)</li><li>No errors in the segments</li><li>Genome is random (No duplicate starts or ends for 16 symbols of segments)</li><li>Segments will be 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 2; 2 2 3 1; 3 1 1 2] creates [0 1 2 2 3 1 1 2] M=3,W=4, Overlap=2Future: Flipped segments, Random Position of Segment start locations, 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 (Matlab - 19.2 sec single thread benchmark)

This Challenge series will evolve the complexity of Genome DNA Sequencing. <http://en.wikipedia.org/wiki/Genome DNA Sequencing> and the <http://en.wikipedia.org/wiki/Shotgun_sequencing Shot Gun Method> will be naively simplified into Cody Challenges. <http://en.wikipedia.org/wiki/Genome_sequence Genome sizes> 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 and duplicative 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:* G = ACGTCGGCCATGGACATTACG

Given three overlapping pieces,  ACGTCGGCCA, GGCCATGGACAT, and GACATTACG these can be readily seen to overlap and create the original.

ACGTCGGCCATGGACATTACG
  ACGTCGGCCAsssssssssss
  sssssGGCCATGGACATssss
  ssssssssssssGACATTACG

Genome_001 Challenge is to reconstruct a genome under ideal segment creation conditions.

# Length of each segment - 48
# Segments begin at locations 1, 33, 65,...32N+1 (N=0:K, L_Genome=32K+48)
# All segments are provided once (Essentially two copies of a genome were cut into pieces with overlaps)
# Segments read left to right (no flips)
# No errors in the segments
# Genome is random (No duplicate starts or ends for 16 symbols of segments)
# Segments will be scrambled

*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 2; 2 2 3 1; 3 1 1 2] creates [0 1 2 2 3 1 1 2] M=3,W=4, Overlap=2

*Future:* Flipped segments, Random Position of Segment start locations, 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 (Matlab - 19.2 sec single thread benchmark)

Solve

Solution Stats

29 Solutions
7 Solvers

Last Solution submitted on Jul 16, 2021

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Are Mjaavatten on 19 Jul 2021 at 9:09

Be aware that one or more test cases are not shown on the "Solve" page, These may have different values for the parameter L.

Problem Recent Solvers7

Problem Tags

Community Treasure Hunt

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

Start Hunting!