Title :
Optimistically building a consensus sequence using ℱ-inexact matches [DNA]
Author :
Cull, P. ; Holloway, J.L.
Author_Institution :
Dept. of Comput. Sci., Oregon State Univ., Corvallis, OR, USA
Abstract :
Biological and physical limitations require that DNA be sequenced in fragments. During the process of sequencing the DNA, errors are occasionally introduced. This paper addresses the problem of reconstructing the original DNA sequence given only the fragments that may contain errors. The authors give a new algorithm based on suffix arrays to solve the problem of reconstructing the original DNA sequence. A worst-case and expected-case time analysis of the algorithm is presented. A program based on this algorithm is used to reconstruct the human beta globin region on chromosome 11 (HUMHBB in GenBank) when given a set of 300 to 500 mers drawn randomly from the HUMHBB locus
Keywords :
DNA; biology computing; errors; DNA sequence; F-inexact matches; GenBank; HUMHBB locus; chromosome 11; errors; fragments; human beta globin; optimistic consensus sequence reconstruction; suffix arrays; Assembly; Biological cells; Biology; Computer errors; Computer science; DNA; Humans; Lead; RNA; Sequences;
Conference_Titel :
System Sciences, 1992. Proceedings of the Twenty-Fifth Hawaii International Conference on
Conference_Location :
Kauai, HI
Print_ISBN :
0-8186-2420-5
DOI :
10.1109/HICSS.1992.183217