NDLI: A new approach to sequence comparison: normalized sequence alignment

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

A new approach to sequence comparison: normalized sequence alignment

Content Provider	ACM Digital Library
Author	Arslan, Abdullah N. Eğecioğlu, Ömer Pevzner, Pavel A.
Abstract	The Smith-Waterman algorithm for local sequence alignment is one of the most important techniques in computational molecular biology. This ingenious dynamic programming approach was designed to reveal the highly conserved fragments by discarding poorly conserved initial and terminal segments. However, the existing notion of local similarity has a serious flaw: it does not discard poorly conserved intermediate segments. The Smith-Waterman algorithm finds the local alignment with maximal score but it is unable to find local alignment with maximum degree of similarity (e.g., maximal percent of matches). Moreover, there is still no efficient algorithm that answers the following natural question: do two sequences share a (sufficiently long) fragment with more than 70% of similarity? As a result, the local alignment sometimes produces a mosaic of well-conserved fragments artificially connected by poorly-conserved or even unrelated fragments. This may lead to problems in comparison of long genomic sequences and comparative gene prediction as recently pointed out by Zhang et al., 1999 [33]. In this paper we propose a new sequence comparison algorithm (normalized local alignment) that reports the regions with maximum degree of similarity. The algorithm is based on fractional programming and its running time is $&Ogr;(n^{2}$ log n). In practice, normalized local alignment is only 3-5 times slower than the standard Smith-Waterman algorithm.
Starting Page	2
Ending Page	11
Page Count	10
File Format	PDF
ISBN	1581133537
DOI	10.1145/369133.369146
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-04-22
Publisher Place	New York
Access Restriction	Subscribed
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