De Novo Repeat Classification and Fragment Assembly

Overview

Journal Genome Res

Specialty Genetics

Date 2004 Sep 3

PMID 15342561

Citations 81

Authors

Pavel A Pevzner

Paul A Pevzner

Haixu Tang

Glenn Tesler

Affiliations

Soon will be listed here.

Abstract

Repetitive sequences make up a significant fraction of almost any genome, and an important and still open question in bioinformatics is how to represent all repeats in DNA sequences. We propose a new approach to repeat classification that represents all repeats in a genome as a mosaic of sub-repeats. Our key algorithmic idea also leads to new approaches to multiple alignment and fragment assembly. In particular, we show that our FragmentGluer assembler improves on Phrap and ARACHNE in assembly of BACs and bacterial genomes.

Citing Articles

GenomeDecoder: inferring segmental duplications in highly repetitive genomic regions.

Zhang Z, Gupta I, Pevzner P Bioinformatics. 2025; 41(2).

PMID: 39908455 PMC: 11842051. DOI: 10.1093/bioinformatics/btaf058.

Maximum-scoring path sets on pangenome graphs of constant treewidth.

Brejova B, Gagie T, Herencsarova E, Vinar T Front Bioinform. 2024; 4:1391086.

PMID: 39011297 PMC: 11246863. DOI: 10.3389/fbinf.2024.1391086.

KaMRaT: a C++ toolkit for k-mer count matrix dimension reduction.

Xue H, Gallopin M, Marchet C, Nguyen H, Wang Y, Laine A Bioinformatics. 2024; 40(3).

PMID: 38444086 PMC: 10942800. DOI: 10.1093/bioinformatics/btae090.

Phables: from fragmented assemblies to high-quality bacteriophage genomes.

Mallawaarachchi V, Roach M, Decewicz P, Papudeshi B, Giles S, Grigson S Bioinformatics. 2023; 39(10).

PMID: 37738590 PMC: 10563150. DOI: 10.1093/bioinformatics/btad586.

Fully automated annotation of mitochondrial genomes using a cluster-based approach with de Bruijn graphs.

Fiedler L, Middendorf M, Bernt M Front Genet. 2023; 14:1250907.

PMID: 37636259 PMC: 10448254. DOI: 10.3389/fgene.2023.1250907.

References

Thompson J, Higgins D, Gibson T . CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res. 1994; 22(22):4673-80. PMC: 308517. DOI: 10.1093/nar/22.22.4673. View

Huang X . A contig assembly program based on sensitive detection of fragment overlaps. Genomics. 1992; 14(1):18-25. DOI: 10.1016/s0888-7543(05)80277-0. View

Myers E . Toward simplifying and accurately formulating fragment assembly. J Comput Biol. 1995; 2(2):275-90. DOI: 10.1089/cmb.1995.2.275. View

Idury R, Waterman M . A new algorithm for DNA sequence assembly. J Comput Biol. 1995; 2(2):291-306. DOI: 10.1089/cmb.1995.2.291. View

Huang X . An improved sequence assembly program. Genomics. 1996; 33(1):21-31. DOI: 10.1006/geno.1996.0155. View

Morgenstern B, Dress A, Werner T . Multiple DNA and protein sequence alignment based on segment-to-segment comparison. Proc Natl Acad Sci U S A. 1996; 93(22):12098-103. PMC: 37949. DOI: 10.1073/pnas.93.22.12098. View

Delcher A, Kasif S, Fleischmann R, Peterson J, White O, Salzberg S . Alignment of whole genomes. Nucleic Acids Res. 1999; 27(11):2369-76. PMC: 148804. DOI: 10.1093/nar/27.11.2369. View

Li X, Waterman M . Estimating the repeat structure and length of DNA sequences using L-tuples. Genome Res. 2003; 13(8):1916-22. PMC: 403783. DOI: 10.1101/gr.1251803. View

Perl A, Colombo E, Samoilova E, Butler M, Banki K . Human transaldolase-associated repetitive elements are transcribed by RNA polymerase III. J Biol Chem. 2000; 275(10):7261-72. DOI: 10.1074/jbc.275.10.7261. View

10.

Myers E, Sutton G, Delcher A, Dew I, Fasulo D, Flanigan M . A whole-genome assembly of Drosophila. Science. 2000; 287(5461):2196-204. DOI: 10.1126/science.287.5461.2196. View

11.

Kurtz S, Ohlebusch E, Schleiermacher C, Stoye J, Giegerich R . Computation and visualization of degenerate repeats in complete genomes. Proc Int Conf Intell Syst Mol Biol. 2000; 8:228-38. View

12.

Bedell J, Korf I, Gish W . MaskerAid: a performance enhancement to RepeatMasker. Bioinformatics. 2001; 16(11):1040-1. DOI: 10.1093/bioinformatics/16.11.1040. View

13.

Pevzner P, Tang H . Fragment assembly with double-barreled data. Bioinformatics. 2001; 17 Suppl 1:S225-33. DOI: 10.1093/bioinformatics/17.suppl_1.s225. View

14.

Pevzner P, Tang H, Waterman M . An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci U S A. 2001; 98(17):9748-53. PMC: 55524. DOI: 10.1073/pnas.171285098. View

15.

Volfovsky N, Haas B, Salzberg S . A clustering method for repeat analysis in DNA sequences. Genome Biol. 2001; 2(8):RESEARCH0027. PMC: 55324. DOI: 10.1186/gb-2001-2-8-research0027. View

16.

Kurtz S, Choudhuri J, Ohlebusch E, Schleiermacher C, Stoye J, Giegerich R . REPuter: the manifold applications of repeat analysis on a genomic scale. Nucleic Acids Res. 2001; 29(22):4633-42. PMC: 92531. DOI: 10.1093/nar/29.22.4633. View

17.

Bailey J, Yavor A, Viggiano L, Misceo D, Horvath J, Archidiacono N . Human-specific duplication and mosaic transcripts: the recent paralogous structure of chromosome 22. Am J Hum Genet. 2001; 70(1):83-100. PMC: 419985. DOI: 10.1086/338458. View

18.

Batzoglou S, Jaffe D, Stanley K, Butler J, Gnerre S, Mauceli E . ARACHNE: a whole-genome shotgun assembler. Genome Res. 2002; 12(1):177-89. PMC: 155255. DOI: 10.1101/gr.208902. View

19.

Lee C, Grasso C, Sharlow M . Multiple sequence alignment using partial order graphs. Bioinformatics. 2002; 18(3):452-64. DOI: 10.1093/bioinformatics/18.3.452. View

20.

Wang J, Wong G, Ni P, Han Y, Huang X, Zhang J . RePS: a sequence assembler that masks exact repeats identified from the shotgun data. Genome Res. 2002; 12(5):824-31. PMC: 186573. DOI: 10.1101/gr.165102. View