CAR: contig assembly of prokaryotic draft genomes using rearrangements

详细信息    查看全文

• 作者：Chin Lung Lu (1)
  Kun-Tze Chen (1)
  Shih-Yuan Huang (1)
  Hsien-Tai Chiu (2)
  
  1. Department of Computer Science ; National Tsing Hua University ; Hsinchu ; 300 ; Taiwan
  2. Department of Chemistry ; National Cheng Kung University ; Tainan City ; 701 ; Taiwan
  
• 关键词：Bioinformatics ; Contig assembly ; Rearrangement
• 刊名：BMC Bioinformatics
• 出版年：2014
• 出版时间：December 2014
• 年：2014
• 卷：15
• 期：1
• 全文大小：2,147 KB
• 参考文献：1. Pop, M, Kosack, DS, Salzberg, SL (2004) Hierarchical scaffolding with Bambus. Genome Res 14: pp. 149-159 CrossRef
  2. Dayarian, A, Michael, TP, Sengupta, AM (2010) SOPRA: scaffolding algorithm for paired reads via statistical optimization. BMC Bioinformatics 11: pp. 345 CrossRef
  3. Boetzer, M, Henkel, CV, Jansen, HJ, Butler, D, Pirovano, W (2011) Scaffolding pre-assembled contigs using SSPACE. Bioinformatics 27: pp. 578-579 CrossRef
  4. Huson, DH, Reinert, K, Myers, EW (2002) The greedy path-merging algorithm for contig scaffolding. J ACM 49: pp. 603-615 CrossRef
  5. Bentley, DR (2006) Whole-genome re-sequencing. Curr Opin Genet Dev 16: pp. 545-552 CrossRef
  6. van Hijum, SA, Zomer, AL, Kuipers, OP, Kok, J (2005) Projector 2 contig mapping for efficient gap-closure of prokaryotic genome sequence assemblies. Nucleic Acids Res 33: pp. W560-W566 CrossRef
  7. Richter, DC, Schuster, SC, Huson, DH (2007) OSLay: optimal syntenic layout of unfinished assemblies. Bioinformatics 23: pp. 1573-1579 CrossRef
  8. Assefa, S, Keane, TM, Otto, TD, Newbold, C, Berriman, M (2009) ABACAS algorithm-based automatic contiguation of assembled sequences. Bioinformatics 25: pp. 1968-1969 CrossRef
  9. Rissman, AI, Mau, B, Biehl, BS, Darling, AE, Glasner, JD, Perna, NT (2009) Reordering contigs of draft genomes using the Mauve Aligner. Bioinformatics 25: pp. 2071-2073 CrossRef
  10. Mu帽oz, A, Zheng, CF, Zhu, QA, Albert, VA, Rounsley, S, Sankoff, D (2010) Scaffold filling, contig fusion and comparative gene order inference. BMC Bioinformatics 11: pp. 304 CrossRef
  11. Husemann, P, Stoye, J (2010) r2cat: synteny plots and comparative assembly. Bioinformatics 26: pp. 570-571 CrossRef
  12. Galardini, M, Biondi, EG, Bazzicalupo, M, Mengoni, A (2011) CONTIGuator: a bacterial genomes finishing tool for structural insights on draft genomes. Source Code Biol Med 6: pp. 11 CrossRef
  13. Dias, Z, Dias, U, Setubal, JC (2012) SIS: a program to generate draft genome sequence scaffolds for prokaryotes. BMC Bioinformatics 13: pp. 96 CrossRef
  14. Li, CL, Chen, KT, Lu, CL (2013) Assembling contigs in draft genomes using reversals and block-interchanges. BMC Bioinformatics 14 Suppl 5: pp. S9 CrossRef
  15. Fertin G, Labarre A, Rusu I, Tannier E, Vialette S: / Combinatorics of Genome Rearrangements, Cambridge: The MIT Press; 2009.
  16. Gaul, E, Blanchette, M (2006) Ordering partially assembled genomes using gene arrangements. Lect Notes Comput Sci 4205: pp. 113-128 CrossRef
  17. Huang, YL, Lu, CL (2010) Sorting by reversals, generalized transpositions, and translocations using permutation groups. J Comput Biol 17: pp. 685-705 CrossRef
  18. Huang, YL, Huang, CC, Tang, CY, Lu, CL (2010) SoRT 2 : a tool for sorting genomes and reconstructing phylogenetic trees by reversals, generalized transpositions and translocations. Nucleic Acids Res 38: pp. W221-W227 CrossRef
  19. Blanchette, M, Kunisawa, T, Sankoff, D (1996) Parametric genome rearrangement. Gene 172: pp. GC11-GC17 CrossRef
  20. Eriksen, N (2002) (1+ 蔚 )-approximation of sorting by reversals and transpositions. Theor Comput Sci 289: pp. 517-529 CrossRef
  21. Kurtz, S, Phillippy, A, Delcher, AL, Smoot, M, Shumway, M, Antonescu, C, Salzberg, SL (2004) Versatile and open software for comparing large genomes. Genome Biol 5: pp. R12 CrossRef
  22. Tesler, G (2002) Efficient algorithms for multichromosomal genome rearrangements. J Comput Syst Sci 65: pp. 587-609 CrossRef
  
• 刊物主题：Bioinformatics; Microarrays; Computational Biology/Bioinformatics; Computer Appl. in Life Sciences; Combinatorial Libraries; Algorithms;
• 出版者：BioMed Central
• ISSN：1471-2105

文摘

Background Next generation sequencing technology has allowed efficient production of draft genomes for many organisms of interest. However, most draft genomes are just collections of independent contigs, whose relative positions and orientations along the genome being sequenced are unknown. Although several tools have been developed to order and orient the contigs of draft genomes, more accurate tools are still needed. Results In this study, we present a novel reference-based contig assembly (or scaffolding) tool, named as CAR, that can efficiently and more accurately order and orient the contigs of a prokaryotic draft genome based on a reference genome of a related organism. Given a set of contigs in multi-FASTA format and a reference genome in FASTA format, CAR can output a list of scaffolds, each of which is a set of ordered and oriented contigs. For validation, we have tested CAR on a real dataset composed of several prokaryotic genomes and also compared its performance with several other reference-based contig assembly tools. Consequently, our experimental results have shown that CAR indeed performs better than all these other reference-based contig assembly tools in terms of sensitivity, precision and genome coverage. Conclusions CAR serves as an efficient tool that can more accurately order and orient the contigs of a prokaryotic draft genome based on a reference genome. The web server of CAR is freely available at http://genome.cs.nthu.edu.tw/CAR/ and its stand-alone program can also be downloaded from the same website.