Genomics. 1992 Sep;14(1):18-25.

A contig assembly program based on sensitive detection of fragment overlaps.

Source

Department of Computer Science, Michigan Technological University, Houghton 49931.

Abstract

An effective computer program for assembling DNA fragments, the contig assembly program (CAP), has been developed. In the CAP program, a filter is used to eliminate quickly fragment pairs that could not possibly overlap, a dynamic programming algorithm is applied to compute the maximal-scoring overlapping alignment between each remaining pair of fragments, and a simple greedy approach is employed to assemble fragments in order of alignment scores. To identify the true fragment overlaps, the dynamic programming algorithm uses specially chosen sets of alignment parameters to tolerate sequencing errors and to penalize "mutational" changes between different copies of a repetitive sequence. The performance tests of the program on fragment data from genomic sequencing projects produced satisfactory results. The CAP program is efficient in computer time and memory; it took about 4 h to assemble a set of 1015 fragments into long contigs on a Sun workstation.

PMID:: 1427824; [PubMed - indexed for MEDLINE]

Publication Types, MeSH Terms, Substances

Publication Types

Research Support, U.S. Gov't, Non-P.H.S.

MeSH Terms

Substances

LinkOut - more resources

Full Text Sources

Elsevier Science

Libraries

LinkOut Holdings

Supplemental Content

Save items

Related citations in PubMed

An Assembly Algorithm for DNA Sequence with Repeats. [Sheng Wu Hua Xue Yu Sheng Wu W...]
An Assembly Algorithm for DNA Sequence with Repeats.
Sheng QH, Ding DF. Sheng Wu Hua Xue Yu Sheng Wu Wu Li Xue Bao (Shanghai). 1998; 30(1):53-58.
A global approach for contig construction. [Comput Appl Biosci. 1994]
A global approach for contig construction.
Gleizes A, Hénaut A. Comput Appl Biosci. 1994 Jul; 10(4):401-8.
ReAligner: a program for refining DNA sequence multi-alignments. [J Comput Biol. 1997]
ReAligner: a program for refining DNA sequence multi-alignments.
Anson EL, Myers EW. J Comput Biol. 1997 Fall; 4(3):369-83.
Review Key-string algorithm--novel approach to computational analysis of repetitive sequences in human centromeric DNA. [Croat Med J. 2003]
Review Key-string algorithm--novel approach to computational analysis of repetitive sequences in human centromeric DNA.
Rosandić M, Paar V, Gluncić M, Basar I, Pavin N. Croat Med J. 2003 Aug; 44(4):386-406.
Review Programming cells: towards an automated 'Genetic Compiler'. [Curr Opin Biotechnol. 2010]
Review Programming cells: towards an automated 'Genetic Compiler'.
Clancy K, Voigt CA. Curr Opin Biotechnol. 2010 Aug; 21(4):572-81. Epub 2010 Aug 9.

See reviews... See all...

Cited by 34 PubMed Central articles

A deep insight into the sialotranscriptome of the gulf coast tick, Amblyomma maculatum. [PLoS One. 2011]
A deep insight into the sialotranscriptome of the gulf coast tick, Amblyomma maculatum.
Karim S, Singh P, Ribeiro JM. PLoS One. 2011; 6(12):e28525. Epub 2011 Dec 21.
The quantitative significance of Syntrophaceae and syntrophic partnerships in methanogenic degradation of crude oil alkanes. [Environ Microbiol. 2011]
The quantitative significance of Syntrophaceae and syntrophic partnerships in methanogenic degradation of crude oil alkanes.
Gray ND, Sherry A, Grant RJ, Rowan AK, Hubert CR, Callbeck CM, Aitken CM, Jones DM, Adams JJ, Larter SR, et al. Environ Microbiol. 2011 Nov; 13(11):2957-75. Epub 2011 Sep 14.
Evolution of the rpoB-psbZ region in fern plastid genomes: notable structural rearrangements and highly variable intergenic spacers. [BMC Plant Biol. 2011]
Evolution of the rpoB-psbZ region in fern plastid genomes: notable structural rearrangements and highly variable intergenic spacers.
Gao L, Zhou Y, Wang ZW, Su YJ, Wang T. BMC Plant Biol. 2011 Apr 13; 11:64. Epub 2011 Apr 13.

See all...

Related information

Related Citations
Calculated set of PubMed citations closely related to the selected article(s) retrieved using a word weight algorithm. Related articles are displayed in ranked order from most to least relevant, with the “linked from” citation displayed first.
Compound (MeSH Keyword)
PubChem chemical compound records that are classified under the same Medical Subject Headings (MeSH) controlled vocabulary as the current articles.
Substance (MeSH Keyword)
PubChem chemical substance (submitted) records that are classified under the same Medical Subject Headings (MeSH) controlled vocabulary as the current articles.
Cited in PMC
Full-text articles in the PubMed Central Database that cite the current articles.

Recent activity

Clear Turn Off Turn On

A contig assembly program based on sensitive detection of fragment overlaps.
A contig assembly program based on sensitive detection of fragment overlaps.
Genomics. 1992 Sep ;14(1):18-25.

PubMed
Pathway for isoleucine formation form pyruvate by leucine biosynthetic enzymes i...
Pathway for isoleucine formation form pyruvate by leucine biosynthetic enzymes in leucine-accumulating isoleucine revertants of Serratia marcescens.
J Biochem. 1977 Jul ;82(1):95-103.

PubMed
Escherichia coli RuvA and RuvB proteins specifically interact with Holliday junc...
Escherichia coli RuvA and RuvB proteins specifically interact with Holliday junctions and promote branch migration.
Genes Dev. 1992 Nov ;6(11):2214-20.

PubMed
THE SYNTHESIS OF PROTEINS UPON RIBOSOMES.
THE SYNTHESIS OF PROTEINS UPON RIBOSOMES.
Bull Soc Chim Biol (Paris). 1964 ;46:1399-425.

PubMed
Estimation of levels of gene flow from DNA sequence data.
Estimation of levels of gene flow from DNA sequence data.
Genetics. 1992 Oct ;132(2):583-9.

PubMed

Your browsing activity is empty.

Activity recording is turned off.

Turn recording back on

PubMed

Result Filters

Display Settings:

Send to: