DNA sequencing and restoring malformed sequences

  • Thread starter Atran
  • Start date
  • #1
93
1
I was just reading about DNA sequencing. In my view, DNA can be modeled into an ordered sequence of nucleobases, as if the two strands were joined into a single strand (just like in RNA). The first half of the sequence models the first strand. The four nucleobases are numbered from 0 to 3. Hence, a random sequence S equals (0 1 2 0 1 1 0 3 ...). The length of the sequence is on the order of billions.

Assume the same sequence is malformed (0 0 2 0 1 1 3 3 ...). It's malformed at position 1 and 6. Visualizing the two sequences parallel to each other, restoring the malformed sequence would be an easy computational task.

Am I missing something? I looked through this because I heard of sequencing in the context of NP-completeness in my computational complexity class.
 

Answers and Replies

  • #2
Ygggdrasil
Science Advisor
Insights Author
Gold Member
3,194
3,197
I don't think recognizing mutations is a computationally hard problem (provided the mutation rate is sufficiently low). In the context of genome sequencing, here's a good source that describes one computationally hard problem that had to be addressed in the genome sequencing field (figuring out how to assemble a full DNA sequence from multiple overlapping short fragments of that DNA sequence): http://www.cs.cmu.edu/afs/cs/academic/class/15210-s15/www/lectures/genome-notes.pdf
 

Related Threads on DNA sequencing and restoring malformed sequences

  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
5
Views
8K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
2K
Replies
12
Views
3K
Replies
1
Views
823
Replies
3
Views
2K
Top