NP complete problems are problems whose status is unknown.
It sounds very confusing and quite impossible to be carried out. Parts from another book may have also been added in, and some shreds may be completely unrecognizable. The original copy may have many repeated paragraphs, and some shreds may be modified during shredding to have typos.
Furthermore, there are some extra practical issues as well. It is obvious that this task is pretty difficult. The sequence assembly problem can be compared to a real life scenario as follows.Īssume that you take many copies of a book, pass each of them through a shredder with a different cutter, and then you try to make the text of the book back together just by gluing together the shredded pieces. This problem is further complicated due to the existence of repetitive sequences in the genome as well as substitutions or mutations withing them. Given a set of sequences, find the minimal length string containing all members of the set as substrings. The sequence assembly problem can be described as follows. In order to obtain the whole genome sequence, we may need to generate more and more random reads, until the contigs match to the target genome. The process of aligning and merging fragments from a longer DNA sequence, in order to reconstruct the original sequence is known as Sequence Assembly. These contigs can be the whole target genome itself, or parts of the genome (as shown in the above figure).
Base sequence analysis software#
Special software are used to assemble these reads according to how they overlap, in order to generate continuous strings called contigs. It reads small pieces of between 0 bases, depending on the technology used. Current DNA sequencing technologies cannot read one whole genome at once. Special machines, known as sequencing machines are used to extract short random DNA sequences from a particular genome we wish to determine ( target genome).
0 kommentar(er)
