NDLI: Separating repeats in DNA sequence assembly

Please wait, while we are loading the content...

The sequence of the human genome (abstract only)

A new approach to sequence comparison: normalized sequence alignment

Context-specific Bayesian clustering for gene expression data

An optimal procedure for gap closing in whole genome shotgun sequencing

Class discovery in gene expression data

On the predictive power of sequence similarity in yeast

Algorithms for phylogenetic footprinting

Predicting the β-helix fold from protein sequence data

Information processing by cells and biologists (abstract only)

Finding motifs using random projections

Rapid significance estimation in local sequence alignment with gaps

Regulatory element detection using correlation with expression (abstract only)

Gene-finding via tandem mass spectrometry

Algorithms for identifying protein cross-links via tandem mass spectrometry

Hunger for new technologies, metrics, and spatiotemporal models in functional genomic (abstract only)

Fast recovery of evolutionary trees with thousands of nodes

Geometric algorithms for the analysis of 2D-electrophoresis gels

Analysis techniques for microarray time-series data

A structural EM algorithm for phylogenetic inference

Optimal sequencing by hybridization in rounds

Efficient algorithms for lateral gene transfer problems

The greedy path-merging algorithm for sequence assembly

Extracting structural information using time-frequency analysis of protein NMR data

Separating repeats in DNA sequence assembly

A NMR-spectra-based scoring function for protein docking

101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem

Comparative analysis of organelle genomes, a biologist's view of computational challenges (abstract only)

DNA segmentation as a model selection process

Edit distance between two RNA structures

Genetics and genemoics: impact on drug discovery and development

The role of computational chemistry in translating genomic information into bioactive small molecules (abstract only)

Comparing sequence scaffolds

Fast and simple character classes and bounded gaps pattern matching, with application to protein searching

Applications of generalized pair hidden Markov models to alignment and gene finding problems

Gene functional classification from heterogeneous data

A new approach to fragment assembly in DNA sequencing

Imposing specificity by regulated localization (abstract only)

Large scale sequencing by hybridization

RNA biology and the genome (abstract only)

Towards predicting coiled-coil protein interactions

Using motion planning to study protein folding pathways

Zinc finger gene clusters and tandem gene duplication

A Gibbs sampling method to detect over-represented motifs in the upstream regions of co-expressed genes

Creating the backbone for the virtual cell (abstract only): cell mapping projects on the run

Creating the backbone for the virtual cell: cell mapping projects on the run

Separating repeats in DNA sequence assembly

Content Provider	ACM Digital Library
Author	Ju, Jun Kececioglu, John
Abstract	One of the key open problems in large-scale DNA sequence assembly is the correct reconstruction of sequences that contain repeats. A long repeat can confound a sequence assembler into falsely overlaying fragments that sample its copies, effectively compressing out the repeat in the reconstructed sequence. We call the task of correcting this compression by separating the overlaid fragments into the distinct copies they sample, the repeat separation problem. We present a rigorous formulation of repeat separation in the general setting without prior knowledge of consensus sequences of repeats or their number of copies. Our formulation decomposes the task into a series of four subproblems, and we design probabilistic tests or combinatorial algorithms that solve each subproblem. The core subproblem separates repeats using the so-called k-median problem in combinatorial optimization, which we solve using integer linear-programming. Experiments with an implementation show we can separate fragments that are overlaid at 10 times the coverage with very few mistakes in a few seconds of computation, even when the sequencing error rate and the error rate between copies are identical. To our knowledge this is the first rigorous and fully general approach to separating repeats that directly addresses the problem.
Starting Page	176
Ending Page	183
Page Count	8
File Format	PDF
ISBN	1581133537
DOI	10.1145/369133.369192
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-04-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Disambiguating repeats k-median problem Shotgun sequencing Computational biology
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in