Sekwencjonowanie i asemblacja dna - podejścia, modele grafowe, algorytmy

• Authors: Marta Kasprzak , Aleksandra Świercz

Title variants

EN

Dna sequencing and assembling - approaches, graph models, and algorithms

• Languages of publication: PL EN

Abstracts

EN

Reading genetic information of an organism, i.e. reading a sequence of nucleotides of a DNA fragment, can be done in two or three stages. In the first stage, the sequencing, one can obtain sequences up to a few hundreds of nucleotides. There are several approaches to carry out this stage. The historically oldest approach is gel electrophoresis, also called by the name of the author - the Sanger method. Another approach is sequencing by hybridization, which is technologically more sophisticated and it involves also algorithmic methods to process the experimental data (as opposed to the previous approach). The novel, fully automated approaches (owned by Roche, Illumina, Applied Biosystems) generate millions of short DNA sequences in short time. Next stage in reading a DNA sequence is the assembling: the output of the sequencing stage is assembled together into longer contigs of length up to even a few million nucleotides. The last stage, called the mapping or the finishing, consists in scheduling assembled sequences in the right order. The methods presented in the paper are only a part of immensely rich literature, which is available for the DNA sequencing and assembling. They were chosen both from the point of view of their importance for the development of this research branch (historically most important approaches and algorithms) and for their attractiveness (interesting graph models). The meaning of the sequencing and the assembling as the first steps on the way of understanding genetic information of organisms, guarantees further development of associated biochemical and computational approaches..

• Journal: Kosmos
• Year: 2009
• Volume: 58
• Issue: 1-2
• Pages: 17-28

Dates

published

2009

Contributors

author

Marta Kasprzak

• Instytut Informatyki, Politechnika Poznańska, Piotrowo 2, 60-965 Poznań, Polska

author

Aleksandra Świercz

• Instytut Informatyki, Politechnika Poznańska, Piotrowo 2, 60-965 Poznań, Polska

References

• Bains W., Smith G. C., 1988. A novel method for nucleic acid sequence determination. J. Theoretical Biology 135, 303-307.
• Bennett S., 2004. Solexa Ltd. Pharmacogenomics 5, 433-438.
• Bergstrom D. E., Andrews P. C., Nichols R., Zhang P., 1995. 3-Nitropyrrole Nucleoside. US Patent No. 5,438,131. 08/01/95.
• Błażewicz J., Kasprzak M., 2003. Complexity of DNA sequencing by hybridization. Theoretical Comput. Sci. 290, 1459-1473.
• Błażewicz J., Kasprzak M., 2006. Computational complexity of isothermic DNA sequencing by hybridization. Discrete Appl. Math. 154, 718-729.
• Błażewicz J., Formanowicz P., 2005. Multistage isothermic sequencing by hybridization. Comput. Biol. Chemistry 29, 69-77.
• Błażewicz J., Formanowicz P., Kasprzak M., Markiewicz W. T., Węglarz J., 1999a. DNA sequencing with positive and negative errors, J. Comput. Biol. 6, 113-123.
• Błażewicz J., Formanowicz P., Kasprzak M., Markiewicz W. T., Węglarz J., 1999b. Method of sequencing of nucleic acids. Polish Patent Application P335786.
• Błażewicz J., Hertz A., Kobler D., de Werra D., 1999c. On some properties of DNA graphs . Discrete Appl. Math. 98, 1-19.
• Błażewicz J., Formanowicz P., Kasprzak M., Jaroszewski M., Markiewicz W. T., 2001. Construction of DNA restriction maps based on a simplified experiment. Bioinformatics 17, 398-404.
• Błażewicz J., Glover F., Kasprzak M., 2004. DNA sequencing - tabu and scatter search combined. INFORMS J. Comput. 16, 232-240.
• Błażewicz J., Oğuz C., Świercz A., Węglarz J., 2006. DNA sequencing by hybridization via Genetic Search. Operations Res. 54, 1185-1192.
• Bui T. N., Youssef W. A, 2004. An enhanced genetic algorithm for DNA sequencing by hybridization with positive and negative errors. Lect. Notes Comput. Sci. 3103, 908-919.
• Chaisson M., Pevzner P., Tang H., 2004. Fragment assembly with short reads. Bioinformatics 20, 2067-2074.
• Fu Y., Peckham H. E., McLaughlin S. F., Rhodes M. D., Malek J. A., McKernan K. J., Blanchard P., 2008. SOLID sequencing and Z-Base encoding. [W:] The Biology of Genomes Meeting, Cold Spring Harbour Laboratory (http://www.appliedbiosystems.com).
• Halperin E., Halperin S., Hartman T., Shamir R., 2003. Handling long targets and errors in sequencing by hybridization. J. Comput. Biol 10, 483-497.
• Heath S. A., Preparata F. P., Young J., 2003. Sequencing by hybridization by cooperating direct and reverse spectra. J. Comput. Biol 10, 499-508.
• Idury R., Waterman M., 1995. A new algorithm for DNA sequence assembly. J. Comput. Biol 2, 291-306.
• Jiang T., Li M., 1996. DNA sequencing and string learning. Math. Systems Theory 29, 387-405.
• Kececioglu J. D., Myers E. W., 1995. Combinatorial algorithms for DNA sequence assembly. Algorithmica 13,7-51.
• Kruglyak S., 1998. Multistage sequencing by hybridization. J. Comput. Biol 5,165-171.
• Loakes D., Brown D. M., 1994. 5-Nitroindole as an universal base analogue. Nucl. Acids Res. 22, 4039-4043.
• Lysov Y. P., Florentiev V. L., Khorlin A. A, Khrapko K. R., Shik V. V., Mirzabekov A. D., 1988. Determination of the nucleotide sequence of DNA using hybridization of oligonucleotides. A new method. Dokl. Akademii Nauk SSSR 303, 1508-1511.
• Margulies M., Egholm M., Altman W. E., Attiya S. i współaut., 2005. Genome sequencing in microfabricated high density picolitre reactors. Nature 437, 376-380.
• Maxam A. M., Gilbert W., 1977. A new method for sequencing DNA. Proc. Natl. Acad. Sci. USA 74, 560-564.
• Pevzner P. A., 1989. l-tuple DNA sequencing: computer analysis. J. Biomol. Struct. Dyn. 7, 63-73.
• Pevzner P., Tang H., Waterman M. S., 2001. A new approach to fragment assembly in DNA sequencing. Proc. 5th Ann. Inter. Conf. Res. Comput. Molecular Biology (RECOMB), ACM Press, Montreal, 256-267.
• Phan V. T., Skiena S., 2001. Dealing with errors in interactive sequencing by hybridization. Bioinformatics 17, 862-870.
• Preparata F. P., Upfal E., 2001. System and methods for sequencing by hybridization. United States Patent Application US 2001/0004728. 21/07/2001.
• Preparata F. P., Oliver J. S., 2004. DNA sequencing by hybridization using semi-degenerate bases. J. Comput. Biol. 11, 753-765.
• Preparata F. P., Frieze A. M., Upfal E.,1999. Optimal reconstruction of a sequence from its probes. J. Comput. Biol. 7, 361-368.
• Sanger F., Nickelen S., Coulson A. R., 1977. DNA sequencing with chain-terminating inhibitors. Proc. Natl. Acad. Sci. USA 74, 5463-5467.
• Southern E. M., 1988. United Kingdom Patent Application GB8810400.
• Southern E. M, Maskos U., Elder J. K., 1992. Analyzing and comparing nucleic acid sequences by hybridization to arrays of oligonucleotides: evaluation using experimental models. Genomics 13, 1008-1017.
• Wallace R. B., Johnson M. J., Hirose T., Miyake T., Kawashima E. H., Itakura K., 1981. The use of synthetic oligonucleotides as hybridization probes. II. Hybridization of oligonucleotides of mixed sequence to rabbit beta-globin DNA. Nucleic Acids Res. 9, 879-894.
• Zerbino D. R., Birney E., 2008. Velvet: Algorithms for de novo short read assembly using de Bruijn graphs. Genome Res. 18, 821-829.
• Zhang J.-H., Wu L.-Y., Zhang X.-S., 2003. Reconstruction of DNA sequencing by hybridization. Bioinformatics 19, 14-21.