Comput Appl Biosci. 1988 Mar;4(1):11-7.

Optimal alignments in linear space.

Source

Department of Computer Science, University of Arizona, Tucson 85721.

Abstract

Space, not time, is often the limiting factor when computing optimal sequence alignments, and a number of recent papers in the biology literature have proposed space-saving strategies. However, a 1975 computer science paper by Hirschberg presented a method that is superior to the new proposals, both in theory and in practice. The goal of this paper is to give Hirschberg's idea the visibility it deserves by developing a linear-space version of Gotoh's algorithm, which accommodates affine gap penalties. A portable C-software package implementing this algorithm is available on the BIONET free of charge.

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

Publication Types, MeSH Terms

Publication Types

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

MeSH Terms

Supplemental Content

Related citations

Introducing variable gap penalties to sequence alignment in linear space. [Comput Appl Biosci. 1995]
Introducing variable gap penalties to sequence alignment in linear space.
Thompson JD. Comput Appl Biosci. 1995 Apr; 11(2):181-6.
Local sequence alignments with monotonic gap penalties. [Bioinformatics. 1999]
Local sequence alignments with monotonic gap penalties.
Mott R. Bioinformatics. 1999 Jun; 15(6):455-62.
Reduced space sequence alignment. [Comput Appl Biosci. 1997]
Reduced space sequence alignment.
Grice JA, Hughey R, Speck D. Comput Appl Biosci. 1997 Feb; 13(1):45-53.
Recent developments in linear-space alignment methods: a survey. [J Comput Biol. 1994]
Recent developments in linear-space alignment methods: a survey.
Chao KM, Hardison RC, Miller W. J Comput Biol. 1994 Winter; 1(4):271-91.
Review Sequence alignment and penalty choice. Review of concepts, case studies and implications. [J Mol Biol. 1994]
Review Sequence alignment and penalty choice. Review of concepts, case studies and implications.
Vingron M, Waterman MS. J Mol Biol. 1994 Jan 7; 235(1):1-12.

See reviews... See all...

Cited by over 100 PubMed Central articles

VIRsiRNAdb: a curated database of experimentally validated viral siRNA/shRNA. [Nucleic Acids Res. 2012]
VIRsiRNAdb: a curated database of experimentally validated viral siRNA/shRNA.
Thakur N, Qureshi A, Kumar M. Nucleic Acids Res. 2012 Jan; 40(Database issue):D230-6. Epub 2011 Dec 1.
Whole-genome comparison of two Campylobacter jejuni isolates of the same sequence type reveals multiple loci of different ancestral lineage. [PLoS One. 2011]
Whole-genome comparison of two Campylobacter jejuni isolates of the same sequence type reveals multiple loci of different ancestral lineage.
Biggs PJ, Fearnhead P, Hotter G, Mohan V, Collins-Emerson J, Kwan E, Besser TE, Cookson A, Carter PE, French NP. PLoS One. 2011; 6(11):e27121. Epub 2011 Nov 11.
Comparative analysis of miRNAs and their targets across four plant species. [BMC Res Notes. 2011]
Comparative analysis of miRNAs and their targets across four plant species.
Lenz D, May P, Walther D. BMC Res Notes. 2011 Nov 8; 4:483. Epub 2011 Nov 8.

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.
Cited in PMC
Full-text articles in the PubMed Central Database that cite the current articles.

Recent activity

Clear Turn Off Turn On

Optimal alignments in linear space.
Optimal alignments in linear space.
Comput Appl Biosci. 1988 Mar ;4(1):11-7.

PubMed
The facts about the phthalates scare.
The facts about the phthalates scare.
Prof Care Mother Child. 1996 ;6(5):126-7.

PubMed
Modulation of tubulin polypeptide ratios by the yeast protein Pac10p.
Modulation of tubulin polypeptide ratios by the yeast protein Pac10p.
Genetics. 1998 Jun ;149(2):857-64.

PubMed
Fibrin: mediator of in vivo and in vitro injury and inflammation.
Fibrin: mediator of in vivo and in vitro injury and inflammation.
Curr Eye Res. 1985 May ;4(5):537-53.

PubMed
Association of apolipoprotein E with alpha2-macroglobulin in human plasma.
Association of apolipoprotein E with alpha2-macroglobulin in human plasma.
J Lipid Res. 1998 Dec ;39(12):2373-86.

PubMed

Your browsing activity is empty.

Activity recording is turned off.

Turn recording back on

PubMed

Display Settings:

Send to:

Optimal alignments in linear space.

Source

Abstract

Publication Types, MeSH Terms

Publication Types

MeSH Terms

Supplemental Content

Related citations

Cited by over 100 PubMed Central articles

Related information

Recent activity

Simple NCBI Directory

Getting Started

Resources

Popular

Featured

NCBI Information