Home LiteratureArticle Details

PMID: 15342561 Published · ppublish English Journal Article Research Support, U.S. Gov't, P.H.S.

De novo repeat classification and fragment assembly.

Genome research ·Vol. 14 ·No. 9 ·2004-09-00 ·Pages 1786-96

Pevzner PA, Pevzner PA, Tang H, Tesler G

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.

MeSH Terms

Algorithms Chromosomes, Artificial, Bacterial Cluster Analysis Computational Biology/methods,statistics & numerical data Contig Mapping/methods Genetic Linkage/genetics Genome, Human Humans Multigene Family/genetics Repetitive Sequences, Nucleic Acid/genetics Sequence Alignment/methods,statistics & numerical data

Authors & Affiliations

4 authors, click to expand affiliations / ORCID

Pevzner Pavel A

Department of Computer Science and Engineering, University of California, San Diego, La Jolla, California 92093, USA.

Pevzner Paul A

Tang Haixu

Tesler Glenn

References (30)

30 references, click to expand

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 Nov 11;22(22):4673-80 PMID: 7984417
A contig assembly program based on sensitive detection of fragment overlaps.
Genomics. 1992 Sep;14(1):18-25 PMID: 1427824
Toward simplifying and accurately formulating fragment assembly.
J Comput Biol. 1995 Summer;2(2):275-90 PMID: 7497129
A new algorithm for DNA sequence assembly.
J Comput Biol. 1995 Summer;2(2):291-306 PMID: 7497130
An improved sequence assembly program.
Genomics. 1996 Apr 1;33(1):21-31 PMID: 8617506
Multiple DNA and protein sequence alignment based on segment-to-segment comparison.
Proc Natl Acad Sci U S A. 1996 Oct 29;93(22):12098-103 PMID: 8901539
Alignment of whole genomes.
Nucleic Acids Res. 1999 Jun 1;27(11):2369-76 PMID: 10325427
Estimating the repeat structure and length of DNA sequences using L-tuples.
Genome Res. 2003 Aug;13(8):1916-22 PMID: 12902383
Human transaldolase-associated repetitive elements are transcribed by RNA polymerase III.
J Biol Chem. 2000 Mar 10;275(10):7261-72 PMID: 10702296
A whole-genome assembly of Drosophila.
Science. 2000 Mar 24;287(5461):2196-204 PMID: 10731133
Computation and visualization of degenerate repeats in complete genomes.
Proc Int Conf Intell Syst Mol Biol. 2000;8:228-38 PMID: 10977084
MaskerAid: a performance enhancement to RepeatMasker.
Bioinformatics. 2000 Nov;16(11):1040-1 PMID: 11159316
Fragment assembly with double-barreled data.
Bioinformatics. 2001;17 Suppl 1:S225-33 PMID: 11473013
An Eulerian path approach to DNA fragment assembly.
Proc Natl Acad Sci U S A. 2001 Aug 14;98(17):9748-53 PMID: 11504945
A clustering method for repeat analysis in DNA sequences.
Genome Biol. 2001;2(8):RESEARCH0027 PMID: 11532211
REPuter: the manifold applications of repeat analysis on a genomic scale.
Nucleic Acids Res. 2001 Nov 15;29(22):4633-42 PMID: 11713313
Human-specific duplication and mosaic transcripts: the recent paralogous structure of chromosome 22.
Am J Hum Genet. 2002 Jan;70(1):83-100 PMID: 11731936
ARACHNE: a whole-genome shotgun assembler.
Genome Res. 2002 Jan;12(1):177-89 PMID: 11779843
Multiple sequence alignment using partial order graphs.
Bioinformatics. 2002 Mar;18(3):452-64 PMID: 11934745
RePS: a sequence assembler that masks exact repeats identified from the shotgun data.
Genome Res. 2002 May;12(5):824-31 PMID: 11997349
Splicing graphs and EST assembly problem.
Bioinformatics. 2002;18 Suppl 1:S181-8 PMID: 12169546
Automated de novo identification of repeat sequence families in sequenced genomes.
Genome Res. 2002 Aug;12(8):1269-76 PMID: 12176934
Whole-genome shotgun assembly and analysis of the genome of Fugu rubripes.
Science. 2002 Aug 23;297(5585):1301-10 PMID: 12142439
A computational method for resequencing long DNA targets by universal oligonucleotide arrays.
Proc Natl Acad Sci U S A. 2002 Nov 26;99(24):15492-6 PMID: 12429861
The phusion assembler.
Genome Res. 2003 Jan;13(1):81-90 PMID: 12529309
The Repeat Pattern Toolkit (RPT): analyzing the structure and evolution of the C. elegans genome.
Proc Int Conf Intell Syst Mol Biol. 1994;2:1-9 PMID: 7584377
Hierarchical scaffolding with Bambus.
Genome Res. 2004 Jan;14(1):149-59 PMID: 14707177
An Eulerian path approach to global multiple alignment for DNA sequences.
J Comput Biol. 2003;10(6):803-19 PMID: 14980012
Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse, and rat genomes.
Genome Res. 2004 Apr;14(4):507-16 PMID: 15059991
1-Tuple DNA sequencing: computer analysis.
J Biomol Struct Dyn. 1989 Aug;7(1):63-73 PMID: 2684223

Article Info

Journal

Genome research

Abbr.

Genome Res

ISSN

1088-9051

DOI

10.1101/gr.2395204

Published

2004-09-00

Pages

1786-96

Language

English

Region

United States

NLM ID

9518021

PMCID

PMC515325

Subset

Grants

NHGRI NIH HHS · R01 HG002366 · United States

NHGRI NIH HHS · 1 R01 HG02366 · United States

Corrections

ErratumIn

External Links

PubMed source DOI: 10.1101/gr.2395204 PMC Full Text View journal details

Analysis Services

De novo repeat classification and fragment assembly.

Contact

WeChat Official Account