Assembling the SARS-CoV genome - new method based on graph theoretical approach.

• Authors: Jacek Błażewicz , Marek Figlerowicz , Piotr Formanowicz , Marta Kasprzak , Bartosz Nowierski , Rafał Styszyński , Łukasz Szajkowski , Paweł Widera , Mariusz Wiktorczyk
• Languages of publication: EN

Abstracts

EN

Nowadays, scientists may learn a lot about the organisms studied just by analyzing their genetic material. This requires the development of methods of reading genomes with high accuracy. It has become clear that the knowledge of the changes occuring within a viral genome is indispensable for effective fighting of the pathogen. A good example is SARS-CoV, which was a cause of death of many people and frightened the entire world with its fast and hard to prevent propagation. Rapid development of sequencing methods, like shotgun sequencing or sequencing by hybridization (SBH), gives scientists a good tool for reading genomes. However, since sequencing methods can read fragments of up to 1000 bp only, methods for sequence assembling are required in order to read whole genomes. In this paper a new assembling method, based on graph theoretical approach, is presented. The method was tested on SARS-CoV and the results were compared to the outcome of other widely known methods.

Keywords

EN

algorithm; assembling; SARS-CoV; graphs

• Publisher: Polish Biochemical Society
• Journal: Acta Biochimica Polonica
• Year: 2004
• Volume: 51
• Issue: 4
• Pages: 983-993

Dates

published

2004

received

2004-04-26

revised

2004-09-14

accepted

2004-10-05

Contributors

author

Jacek Błażewicz

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

author

Marek Figlerowicz

• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznań, Poland

author

Piotr Formanowicz

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

author

Marta Kasprzak

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

author

Bartosz Nowierski

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

author

Rafał Styszyński

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

author

Łukasz Szajkowski

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

author

Paweł Widera

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

author

Mariusz Wiktorczyk

• Institute of Computing Science, Poznań University of Technology, Poznań, Poland

References

• Bains W. (1991) Hybridization methods for DNA sequencing. Genomics.; 11: 294-301.
• Błażewicz J, Formanowicz P, Kasprzak M, Markiewicz WT, Węglarz J. (1999a) DNA sequencing with positive and negative errors. J Comput Biol.; 6: 113-23.
• Błażewicz J, Formanowicz P, Kasprzak M, Markiewicz WT. (1999b) Method of Sequencing of Nucleic Acids. The Patent Office of the Republic of Poland, Patent Application No. P 335786.
• Błażewicz J, Formanowicz P, Kasprzak M, Markiewicz WT, Węglarz J. (2000) Tabu search for DNA sequencing with false negatives and false positives. Eur J Oper Res.; 125: 257-65.
• Błażewicz J, Formanowicz P, Kasprzak M, Markiewicz WT, Świercz A. (2004a) Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries. Comput Biol Chem.; 28: 11-9.
• Błażewicz J, Kasprzak M, Jackowiak P, Janny D, Jarczyński D, Nalewaj M, Nowierski B, Styszyński R, Szajowski Ł, Widera P. (2004b) ASM - DNA Assembly Application. Report RA-001/2004, Poznan Supercomputing and Networking Center.
• Chin G, Coontz R, Helmuth L. (2004) Biology by the numbers. Science.; 303: 781.
• Cormen TH, Leiserson CE, Rivest RL. (1990) Introduction to Algorithms. MIT Press, Cambridge.
• Farci P, Strazzera R, Alter HJ, Farci S, Degioannis D, Coiana A, Peddis G, Usai F, Serra G, Chessa L, Diaz G, Balestrieri A, Purcell RH. (2002) Early changes in hepatitis C viral quasispecies during interferon therapy predict the therapeutic outcome. Proc Natl Acad Sci USA.; 99: 3081-6.
• Figlerowicz M, Alejska M, Kurzyńska-Kokorniak A, Figlerowicz M. (2003) Genetic variability: the key problem in the prevention and therapy of RNA-based virus infections. Med Res Rev.; 23: 488-518.
• Gusfield D. (1997) Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology. Cambridge University Press, Cambridge.
• Gutin G, Punnen AP, eds. (2002) Travelling Salesman Problem and its Variations. Kluwer Academic Publishers, Dordrecht.
• Marra MA, Jones SJ, Astell CR, Holt RA, Brooks-Wilson A, Butterfield YS, Khattra J, Asano JK, Barber SA, Chan SY, Cloutier A, Coughlin SM, Freeman D, Girn N, Griffith OL, Leach SR, Mayo M, McDonald H, Montgomery SB, Pandoh PK, Petrescu AS, Robertson AG, Schein JE, Siddiqui A, Smailus DE, Stott JM, Yang GS, Plummer F, Andonov A, Artsob H, Bastien N, Bernard K, Booth TF, Bowness D, Czub M, Drebot M, Fernando L, Flick R, Garbutt M, Gray M, Grolla A, Jones S, Feldmann H, Meyers A, Kabani A, Li Y, Normand S, Stroher U, Tipples GA, Tyler S, Vogrig R, Ward D, Watson B, Brunham RC, Krajden M, Petric M, Skowronski DM, Upton C, Roper RL. (2003) The genome sequence of the SARS-associated coronavirus. Science.; 300: 1399-404.
• Myers EW, Sutton GG, Delcher AL, Dew IM, Fasulo DP, Flanigan MJ, Kravitz SA, Mobarry CM, Reinert KHJ, Remington KA, Anson EL, Bolanos RA, Chou HH, Jordan CM, Halpern AL, Lonardi S, Beasley EM, Brandon RC, Chen L, Dunn PJ, Lai ZW, Liang Y, Nusskern DR, Zhan M, Zhang Q, Zheng XQ, Rubin GM, Adams MD, Venter JC. (2000) A whole-genome assembly of Drosophila. Science.; 287: 2196-204.
• Pevzner PA. (2000) Computational Molecular Biology. An Algorithmic Approach. MIT Press, Cambridge, London.
• Richman DD. (2001) HIV chemotherapy. Nature.; 410: 995-1001.
• Rota PA, Oberste MS, Monroe SS, Nix WA, Campagnoli R, Icenogle JP, Penaranda S, Bankamp B, Maher K, Chen MH, Tong SX, Tamin A, Lowe L, Frace M, DeRisi JL, Chen Q, Wang D, Erdman DD, Peret TCT, Burns C, Ksiazek TG, Rollin PE, Sanchez A, Liffick S, Holloway B, Limor J, McCaustland K, Olsen-Rasmussen M, Fouchier R, Gunther S, Osterhaus ADME, Drosten C, Pallansch MA, Anderson LJ, Bellini WJ. (2003) Characterization of a novel coronavirus associated with severe acute respiratory syndrome. Science.; 300: 1394-9.
• Setubal J, Meidanis J. (1997) Introduction to Computational Molecular Biology. PWS Publishing Company, Boston.
• Smith TF, Waterman MS. (1981) Identification of common molecular subsequences. J Mol Biol.; 147: 195-7.
• Southern EM. (1988) United Kingdom Patent Application GB8 810400.
• Waterman MS. (1995) Introduction to Computational Biology. Maps, Sequences and Genomes. Chapman & Hall, London.
• Wilbur WJ, Lipman DJ. (1983) Rapid similarity searches of nucleic acid and protein data banks. Proc Natl Acad Sci USA.; 80: 726-30.