doi: 10.1093/bioinformatics/4.1.11.
Optimal alignments in linear space
Affiliations
- PMID: 3382986
- DOI: 10.1093/bioinformatics/4.1.11
Item in Clipboard
Optimal alignments in linear space
Comput Appl Biosci.
1988 Mar.
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.
Similar articles
-
Introducing variable gap penalties to sequence alignment in linear space.Comput Appl Biosci. 1995 Apr;11(2):181-6. doi: 10.1093/bioinformatics/11.2.181. Comput Appl Biosci. 1995. PMID: 7620991
-
Reduced space sequence alignment.Comput Appl Biosci. 1997 Feb;13(1):45-53. doi: 10.1093/bioinformatics/13.1.45. Comput Appl Biosci. 1997. PMID: 9088708
-
Local sequence alignments with monotonic gap penalties.Bioinformatics. 1999 Jun;15(6):455-62. doi: 10.1093/bioinformatics/15.6.455. Bioinformatics. 1999. PMID: 10383814
-
Recent developments in linear-space alignment methods: a survey.J Comput Biol. 1994 Winter;1(4):271-91. doi: 10.1089/cmb.1994.1.271. J Comput Biol. 1994. PMID: 8790471
-
Sequence alignment and penalty choice. Review of concepts, case studies and implications.J Mol Biol. 1994 Jan 7;235(1):1-12. doi: 10.1016/s0022-2836(05)80006-3. J Mol Biol. 1994. PMID: 8289235 Review.
Cited by
-
Characterization of a GDS(L)-like hydrolase from Pleurotus sapidus with an unusual SGNH motif.AMB Express. 2024 Sep 3;14(1):98. doi: 10.1186/s13568-024-01752-x. AMB Express. 2024. PMID: 39225819 Free PMC article.
-
Soil Application of a Formulated Biocontrol Rhizobacterium, Pseudomonas chlororaphis PCL1606, Induces Soil Suppressiveness by Impacting Specific Microbial Communities.Front Microbiol. 2020 Aug 7;11:1874. doi: 10.3389/fmicb.2020.01874. eCollection 2020. Front Microbiol. 2020. PMID: 32849458 Free PMC article.
-
VIRsiRNAdb: a curated database of experimentally validated viral siRNA/shRNA.Nucleic Acids Res. 2012 Jan;40(Database issue):D230-6. doi: 10.1093/nar/gkr1147. Epub 2011 Dec 1. Nucleic Acids Res. 2012. PMID: 22139916 Free PMC article.
-
CDC55, a Saccharomyces cerevisiae gene involved in cellular morphogenesis: identification, characterization, and homology to the B subunit of mammalian type 2A protein phosphatase.Mol Cell Biol. 1991 Nov;11(11):5767-80. doi: 10.1128/mcb.11.11.5767-5780.1991. Mol Cell Biol. 1991. PMID: 1656238 Free PMC article.
-
Characterization of the terminal regions of hepatitis C viral RNA: identification of conserved sequences in the 5' untranslated region and poly(A) tails at the 3' end.Proc Natl Acad Sci U S A. 1991 Mar 1;88(5):1711-5. doi: 10.1073/pnas.88.5.1711. Proc Natl Acad Sci U S A. 1991. PMID: 1705704 Free PMC article.
Publication types
MeSH terms
LinkOut - more resources
Other Literature Sources
Miscellaneous