Bull Math Biol. 1990;52(3):359-73.

Optimal sequence alignment allowing for long gaps.

Source

Department of Biochemistry, Saitama Cancer Research Institute, Japan.

Abstract

A new algorithm for optimal sequence alignment allowing for long insertions and deletions is developed. The algorithm requires O((L+C)MN) computational steps, O(LN) primary memory and O(MN) secondary memory storage, where M and N(M greater than or equal to N) are sequence lengths, L(typically L less than or greater than 3) is the number of segment specifying the gap weighting function, and C is a constant. We have also modified our earlier traceback algorithm so that it finds all and and only the optimal alignments in a compact form of a directed graph. The current versions accept a set of aligned sequences as input, which facilitates multiple sequence alignment by some iterative procedures.

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

MeSH Terms, Substances

MeSH Terms

Substances

LinkOut - more resources

Full Text Sources

Supplemental Content

Save items

Related citations in PubMed

A linear memory algorithm for Baum-Welch training. [BMC Bioinformatics. 2005]
A linear memory algorithm for Baum-Welch training.
Miklós I, Meyer IM. BMC Bioinformatics. 2005 Sep 19; 6:231. Epub 2005 Sep 19.
Alignment of three biological sequences with an efficient traceback procedure. [J Theor Biol. 1986]
Alignment of three biological sequences with an efficient traceback procedure.
Gotoh O. J Theor Biol. 1986 Aug 7; 121(3):327-37.
Using CLUSTAL for multiple sequence alignments. [Methods Enzymol. 1996]
Using CLUSTAL for multiple sequence alignments.
Higgins DG, Thompson JD, Gibson TJ. Methods Enzymol. 1996; 266:383-402.
A fast homology program for aligning biological sequences. [Nucleic Acids Res. 1984]
A fast homology program for aligning biological sequences.
Taylor P. Nucleic Acids Res. 1984 Jan 11; 12(1 Pt 2):447-55.
An algorithm for progressive multiple alignment of sequences with insertions. [Proc Natl Acad Sci U S A. 2005]
An algorithm for progressive multiple alignment of sequences with insertions.
Löytynoja A, Goldman N. Proc Natl Acad Sci U S A. 2005 Jul 26; 102(30):10557-62. Epub 2005 Jul 6.

See reviews... See all...

Cited by 7 PubMed Central articles

A space-efficient and accurate method for mapping and aligning cDNA sequences onto genomic sequence. [Nucleic Acids Res. 2008]
A space-efficient and accurate method for mapping and aligning cDNA sequences onto genomic sequence.
Gotoh O. Nucleic Acids Res. 2008 May; 36(8):2630-8. Epub 2008 Mar 15.
Dynamic use of multiple parameter sets in sequence alignment. [Nucleic Acids Res. 2007]
Dynamic use of multiple parameter sets in sequence alignment.
Huang X, Brutlag DL. Nucleic Acids Res. 2007; 35(2):678-86. Epub 2006 Dec 19.
Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost. [BMC Bioinformatics. 2006]
Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost.
Yamada S, Gotoh O, Yamana H. BMC Bioinformatics. 2006 Dec 1; 7:524. Epub 2006 Dec 1.

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.
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

Optimal sequence alignment allowing for long gaps.
Optimal sequence alignment allowing for long gaps.
Bull Math Biol. 1990 ;52(3):359-73.

PubMed
Use of complementary and alternative medicine in children with recurrent acute o...
Use of complementary and alternative medicine in children with recurrent acute otitis media in Italy.
Int J Immunopathol Pharmacol. 2011 Apr-Jun ;24(2):441-9.

PubMed
HSV-1 gB and VZV gp-II crossreactive antibodies in human sera.
HSV-1 gB and VZV gp-II crossreactive antibodies in human sera.
Arch Virol. 1990 ;112(3-4):203-13.

PubMed
Membrane-based emitter for coupling microfluidics with ultrasensitive nanoelectr...
Membrane-based emitter for coupling microfluidics with ultrasensitive nanoelectrospray ionization-mass spectrometry.
Anal Chem. 2011 Jul 15 ;83(14):5797-803. Epub 2011 Jun 22 .

PubMed
Evidence for a virtual human analog of a rodent relational memory task: a study ...
Evidence for a virtual human analog of a rodent relational memory task: a study of aging and fMRI in young adults.
Hippocampus. 2012 Apr ;22(4):869-80. doi: 10.1002/hipo.20948. Epub 2011 Jun 8 .

PubMed

Your browsing activity is empty.

Activity recording is turned off.

Turn recording back on

PubMed

Result Filters

Display Settings:

Send to: