The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Optimal alignments in linear space
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The String-to-String Correction Problem
Wagner, R. A., & Fischer, M. J. (1974) · Journal of the ACM · doi:10.1145/321796.321811 · Cited by 3,032
An improved algorithm for matching biological sequences
Gotoh, O. (1982) · Journal of Molecular Biology · doi:10.1016/0022-2836(82)90398-9 · Cited by 1,724
AnO(ND) difference algorithm and its variations
Myers, E. W. (1986) · Algorithmica · doi:10.1007/bf01840446 · Cited by 893
Self-citationA faster algorithm computing string edit distances
Masek, W. J., & Paterson, M. S. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90002-1 · Cited by 651
Algorithms for approximate string matching
Ukkonen, E. (1985) · Information and Control · doi:10.1016/s0019-9958(85)80046-2 · Cited by 610
Some biological sequence metrics
Waterman, M. S., Smith, T. F., & Beyer, W. A. (1976) · Advances in Mathematics · doi:10.1016/0001-8708(76)90202-4 · Cited by 358
Comparative biosequence metrics
Smith, T. F., Waterman, M. S., & Fitch, W. M. (1981) · Journal of Molecular Evolution · doi:10.1007/bf01733210 · Cited by 248
Miller, W., & Myers, E. W. (1985) · Software: Practice and Experience · doi:10.1002/spe.4380151102 · Cited by 186
Self-citationSequence comparison with concave weighting functions
Miller, W., & Myers, E. W. (1988) · Bulletin of Mathematical Biology · doi:10.1007/bf02459948 · Cited by 152
Self-citationFickett, J. W. (1984) · Nucleic Acids Research · doi:10.1093/nar/12.1part1.175 · Cited by 100
Cited by
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
Altschul, S. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.17.3389 · Cited by 73,302
Thompson, J. D., Higgins, D. G., & Gibson, T. J. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.22.4673 · Cited by 64,617
VSEARCH: a versatile open source tool for metagenomics
(2016) · doi:10.7717/peerj.2584 · Cited by 10,773
MUSCLE: a multiple sequence alignment method with reduced time and space complexity
Edgar, R. C. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-113 · Cited by 8,970
Yoon, S.-H., Ha, S.-M., Kwon, S., Lim, J., Kim, Y., Seo, H., & Chun, J. (2017) · International Journal of Systematic and Evolutionary Microbiology · doi:10.1099/ijsem.0.001755 · Cited by 7,702
CAP3: A DNA Sequence Assembly Program
Huang, X., & Madan, A. (1999) · Genome Research · doi:10.1101/gr.9.9.868 · Cited by 5,261
Kim, O.-S., Cho, Y.-J., Lee, K., Yoon, S.-H., Kim, M., Na, H., Park, S.-C., Jeon, Y. S., Lee, J.-H., Yi, H., et al. (2012) · International Journal of Systematic and Evolutionary Microbiology · doi:10.1099/ijs.0.038075-0 · Cited by 5,240
Multiple sequence alignment with the Clustal series of programs
Chenna, R. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkg500 · Cited by 4,875
Recent developments in the MAFFT multiple sequence alignment program
Katoh, K., & Toh, H. (2008) · Briefings in Bioinformatics · doi:10.1093/bib/bbn013 · Cited by 3,586
Multiple Sequence Alignment Using ClustalW and ClustalX
Thompson, J. D., Gibson, T. J., & Higgins, D. G. (2003) · Current Protocols in Bioinformatics · doi:10.1002/0471250953.bi0203s00 · Cited by 2,971
CLUSTAL V: improved software for multiple sequence alignment
Higgins, D. G., Bleasby, A. J., & Fuchs, R. (1992) · Bioinformatics · doi:10.1093/bioinformatics/8.2.189 · Cited by 2,381
Chun, J., Lee, J.-H., Jung, Y., Kim, M., Kim, S., Kim, B. K., & Lim, Y.-W. (2007) · International Journal of Systematic and Evolutionary Microbiology · doi:10.1099/ijs.0.64915-0 · Cited by 2,105
Prediction of protein subcellular localization
Yu, C., Chen, Y., Lu, C., & Hwang, J. (2006) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.21018 · Cited by 1,790
Multiple Alignment of DNA Sequences with MAFFT
Katoh, K., Asimenos, G., & Toh, H. (2009) · Methods in Molecular Biology · doi:10.1007/978-1-59745-251-9_3 · Cited by 1,438
Schaffer, A. A. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.14.2994 · Cited by 1,386
Fast and sensitive multiple sequence alignments on a microcomputer
Higgins, D. G., & Sharp, P. M. (1989) · Bioinformatics · doi:10.1093/bioinformatics/5.2.151 · Cited by 1,218
Collapsin: A protein in brain that induces the collapse and paralysis of neuronal growth cones
Luo, Y., Raible, D., & Raper, J. A. (1993) · Cell · doi:10.1016/0092-8674(93)80064-l · Cited by 1,179
ProbCons: Probabilistic consistency-based multiple sequence alignment
Do, C. B., Mahabhashyam, M. S. P., Brudno, M., & Batzoglou, S. (2005) · Genome Research · doi:10.1101/gr.2821705 · Cited by 1,114
A time-efficient, linear-space local similarity algorithm
Huang, X., & Miller, W. (1991) · Advances in Applied Mathematics · doi:10.1016/0196-8858(91)90017-d · Cited by 1,004
Self-citationA workbench for multiple alignment construction and analysis
Schuler, G. D., Altschul, S. F., & Lipman, D. J. (1991) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.340090304 · Cited by 985
A new DNA sequence assembly program
Bonfield, J. K., Smith, K. F., & Staden, R. (1995) · Nucleic Acids Research · doi:10.1093/nar/23.24.4992 · Cited by 973
An algorithm for progressive multiple alignment of sequences with insertions
Löytynoja, A., & Goldman, N. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0409137102 · Cited by 907
MatGAT: An application that generates similarity/identity matrices using protein or DNA sequences
Campanella, J. J., Bitincka, L., & Smalley, J. (2003) · BMC Bioinformatics · doi:10.1186/1471-2105-4-29 · Cited by 857
Gene networks driving bovine milk fat synthesis during the lactation cycle
Bionaz, M., & Loor, J. J. (2008) · BMC Genomics · doi:10.1186/1471-2164-9-366 · Cited by 785
Issues in searching molecular sequence databases
Altschul, S. F., Boguski, M. S., Gish, W., & Wootton, J. C. (1994) · Nature Genetics · doi:10.1038/ng0294-119 · Cited by 774
Segmental Duplications: Organization and Impact Within the Current Human Genome Project Assembly
Bailey, J. A., Yavor, A. M., Massa, H. F., Trask, B. J., & Eichler, E. E. (2001) · Genome Research · doi:10.1101/gr.187101 · Cited by 717
Mad: A heterodimeric partner for Max that antagonizes Myc transcriptional activity
Ayer, D. E., Kretzner, L., & Eisenman, R. N. (1993) · Cell · doi:10.1016/0092-8674(93)90661-9 · Cited by 703
The novel ATM-related protein TRRAP is an essential cofactor for the c-Myc and E2F oncoproteins
McMahon, S. B., Van Buskirk, H. A., Dugan, K. A., Copeland, T. D., & Cole, M. D. (1998) · Cell · doi:10.1016/s0092-8674(00)81479-8 · Cited by 693
Zhao, Y., Wei, W., Lee, I.-M., Shao, J., Suo, X., & Davis, R. E. (2009) · INTERNATIONAL JOURNAL OF SYSTEMATIC AND EVOLUTIONARY MICROBIOLOGY · doi:10.1099/ijs.0.010249-0 · Cited by 667
Roca, F. J., & Ramakrishnan, L. (2013) · Cell · doi:10.1016/j.cell.2013.03.022 · Cited by 592
Oda, T., Morikawa, N., Saito, Y., Masuho, Y., & Matsumoto, S.-I. (2000) · Journal of Biological Chemistry · doi:10.1074/jbc.m006480200 · Cited by 608
Flexible Sequence Similarity Searching with the FASTA3 Program Package
Pearson, W. R. (2003) · Bioinformatics Methods and Protocols · doi:10.1385/1-59259-192-2:185 · Cited by 600
Lee, I., Chalita, M., Ha, S.-M., Na, S.-I., Yoon, S.-H., & Chun, J. (2017) · International Journal of Systematic and Evolutionary Microbiology · doi:10.1099/ijsem.0.001872 · Cited by 578
Isoleucine synthesis in Corynebacterium glutamicum: molecular analysis of the ilvB-ilvN-ilvC operon
Keilhauer, C., Eggeling, L., & Sahm, H. (1993) · Journal of Bacteriology · doi:10.1128/jb.175.17.5595-5603.1993 · Cited by 563
Edgar, R. C., & Batzoglou, S. (2006) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2006.04.004 · Cited by 517
A tool for multiple sequence alignment.
Lipman, D. J., Altschul, S. F., & Kececioglu, J. D. (1989) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.86.12.4412 · Cited by 506
Holmes, D. E., Bond, D. R., O?Neil, R. A., Reimers, C. E., Tender, L. R., & Lovley, D. R. (2004) · Microbial Ecology · doi:10.1007/s00248-003-0004-4 · Cited by 503
Exploiting the past and the future in protein secondary structure prediction
Baldi, P., Brunak, S., Frasconi, P., Soda, G., & Pollastri, G. (1999) · Bioinformatics · doi:10.1093/bioinformatics/15.11.937 · Cited by 497
Gimeno, R. E., Dembski, M., Weng, X., Deng, N., Shyjan, A. W., Gimeno, C. J., Iris, F., Ellis, S. J., Woolf, E. A., & Tartaglia, L. A. (1997) · Diabetes · doi:10.2337/diab.46.5.900 · Cited by 496
ClustalW-MPI: ClustalW analysis using distributed and parallel computing
Li, K.-B. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg192 · Cited by 468
PCR Detection of Genes Encoding Nitrite Reductase in Denitrifying Bacteria
Hallin, S., & Lindgren, P.-E. (1999) · Applied and Environmental Microbiology · doi:10.1128/aem.65.4.1652-1657.1999 · Cited by 457
An Alu Transposition Model for the Origin and Expansion of Human Segmental Duplications
Bailey, J. A., Liu, G., & Eichler, E. E. (2003) · The American Journal of Human Genetics · doi:10.1086/378594 · Cited by 441
A Model for Arrestin’s Regulation: The 2.8 Å Crystal Structure of Visual Arrestin
Hirsch, J. A., Schubert, C., Gurevich, V. V., & Sigler, P. B. (1999) · Cell · doi:10.1016/s0092-8674(00)80735-7 · Cited by 436
Han, J. H., Shyamala, V, Richman, K. H., Brauer, M. J., Irvine, B., Urdea, M. S., Tekamp-Olson, P., Kuo, G., Choo, Q. L., & Houghton, M. (1991) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.88.5.1711 · Cited by 423
How Well is Enzyme Function Conserved as a Function of Pairwise Sequence Identity?
Tian, W., & Skolnick, J. (2003) · Journal of Molecular Biology · doi:10.1016/j.jmb.2003.08.057 · Cited by 412
Relationship Between the Occurrence of Cysteine in Proteins and the Complexity of Organisms
Miseta, A., & Csutora, P. (2000) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a026406 · Cited by 397
Chun, J., Grim, C. J., Hasan, N. A., Lee, J. H., Choi, S. Y., Haley, B. J., Taviani, E., Jeon, Y.-S., Kim, D. W., Lee, J.-H., et al. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0907787106 · Cited by 384
proseq: A software for preparation and evolutionary analysis of DNA sequence data sets
Filatov, D. A. (2002) · Molecular Ecology Notes · doi:10.1046/j.1471-8286.2002.00313.x · Cited by 373
Wilson, C. A., Kreychman, J., & Gerstein, M. (2000) · Journal of Molecular Biology · doi:10.1006/jmbi.2000.3550 · Cited by 367
Park, K.-J., & Kanehisa, M. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg222 · Cited by 364
Cloning and expression of a human Ah receptor cDNA.
Dolwick, K. M., Schmidt, J. V., Carver, L. A., Swanson, H. I., & Bradfield, C. A. (1993) · Molecular Pharmacology · doi:10.1016/s0026-895x(25)13282-3 · Cited by 348
Protein sequence similarity searches using patterns as seeds
Zhang, Z. (1998) · Nucleic Acids Research · doi:10.1093/nar/26.17.3986 · Cited by 342
Comparison of methods for searching protein sequence databases
Pearson, W. R. (1995) · Protein Science · doi:10.1002/pro.5560040613 · Cited by 336
Van Sluys, M. A., de Oliveira, M. C., Monteiro-Vitorello, C. B., Miyaki, C. Y., Furlan, L. R., Camargo, L. E. A., da Silva, A. C. R., Moon, D. H., Takita, M. A., Lemos, E. G. M., et al. (2003) · Journal of Bacteriology · doi:10.1128/jb.185.3.1018-1026.2003 · Cited by 329
Genome Sequence of a Human Tumorigenic Poxvirus: Prediction of Specific Host Response-Evasion Genes
Senkevich, T. G., Bugert, J. J., Sisler, J. R., Koonin, E. V., Darai, G., & Moss, B. (1996) · Science · doi:10.1126/science.273.5276.813 · Cited by 327
Comparative Studies of Class IIa Bacteriocins of Lactic Acid Bacteria
Eijsink, V. G. H., Skeie, M., Middelhoven, P. H., Brurberg, M. B., & Nes, I. F. (1998) · Applied and Environmental Microbiology · doi:10.1128/aem.64.9.3275-3281.1998 · Cited by 324
A High-Throughput DNA Sequence Aligner for Microbial Ecology Studies
Schloss, P. D. (2009) · PLoS ONE · doi:10.1371/journal.pone.0008230 · Cited by 323
Genome sequence of the chlorinated compound–respiring bacterium Dehalococcoides species strain CBDB1
Kube, M., Beck, A., Zinder, S. H., Kuhl, H., Reinhardt, R., & Adrian, L. (2005) · Nature Biotechnology · doi:10.1038/nbt1131 · Cited by 302
Clustal V: Multiple Alignment of DNA and Protein Sequences
Higgins, D. G. (1994) · Computer Analysis of Sequence Data · doi:10.1385/0-89603-276-0:307 · Cited by 299
A contig assembly program based on sensitive detection of fragment overlaps
Huang, X. (1992) · Genomics · doi:10.1016/s0888-7543(05)80277-0 · Cited by 296
Classification and identification of geminiviruses using sequence comparisons
Padidam, M., Beachy, R. N., & Fauquet, C. M. (1995) · Journal of General Virology · doi:10.1099/0022-1317-76-2-249 · Cited by 294
Nicaise, V., German-Retana, S., Sanjuán, R., Dubrana, M.-P., Mazier, M., Maisonneuve, B., Candresse, T., Caranta, C., & LeGall, O. (2003) · Plant Physiology · doi:10.1104/pp.102.017855 · Cited by 290
Tekamp-Olson, P., Gallegos, C., Bauer, D., McClain, J., Sherry, B., Fabre, M., van Deventer, S., & Cerami, A. (1990) · The Journal of experimental medicine · doi:10.1084/jem.172.3.911 · Cited by 289
Healy, A. M., Zolnierowicz, S., Stapleton, A. E., Goebl, M., DePaoli-Roach, A. A., & Pringle, J. R. (1991) · Molecular and Cellular Biology · doi:10.1128/mcb.11.11.5767 · Cited by 284
EST_GENOME: a program to align spliced DNA sequences to unspliced genomic DNA
Mott, R. (1997) · Bioinformatics · doi:10.1093/bioinformatics/13.4.477 · Cited by 276
Lassmann, T., Frings, O., & Sonnhammer, E. L. L. (2009) · Nucleic Acids Research · doi:10.1093/nar/gkn1006 · Cited by 274
Gao, P., Watanabe, S., Ito, T., Goto, H., Wells, K., McGregor, M., Cooley, A. J., & Kawaoka, Y. (1999) · Journal of Virology · doi:10.1128/jvi.73.4.3184-3189.1999 · Cited by 270
Bascom, R. A., Manara, S., Collins, L., Molday, R. S., Kalnins, V. I., & Mclnnes, R. R. (1992) · Neuron · doi:10.1016/0896-6273(92)90137-3 · Cited by 257
Jang, L.-G., Choi, G., Kim, S.-W., Kim, B.-Y., Lee, S., & Park, H. (2019) · Journal of the International Society of Sports Nutrition · doi:10.1186/s12970-019-0290-y · Cited by 224
The Chlamydomonas FLA10 gene encodes a novel kinesin-homologous protein.
Walther, Z., Vashishtha, M., & Hall, J. L. (1994) · The Journal of cell biology · doi:10.1083/jcb.126.1.175 · Cited by 226
Choi, Y., Kwon, Y., Kim, D.-K., Jeon, J., Jang, S. C., Wang, T., Ban, M., Kim, M.-H., Jeon, S. G., Kim, M.-S., et al. (2015) · Scientific Reports · doi:10.1038/srep15878 · Cited by 218
Mushegian, A. R., Garey, J. R., Martin, J., & Liu, L. X. (1998) · Genome Research · doi:10.1101/gr.8.6.590 · Cited by 164
Low number of fixed somatic mutations in a long-lived oak tree
Schmid-Siegert, E., Sarkar, N., Iseli, C., Calderon, S., Gouhier-Darimont, C., Chrast, J., Cattaneo, P., Schütz, F., Farinelli, L., Pagni, M., et al. (2017) · Nature Plants · doi:10.1038/s41477-017-0066-9 · Cited by 161
Park, M., Choi, J., & Lee, H.-J. (2020) · Nutrients · doi:10.3390/nu12061815 · Cited by 139
Gelfand, M. S., & Koonin, E. V. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.12.2430 · Cited by 134
Kim, J., An, J.-U., Kim, W., Lee, S., & Cho, S. (2017) · Gut Pathogens · doi:10.1186/s13099-017-0218-5 · Cited by 129
Optimal gap-affine alignment in O ( s ) space
Marco-Sola, S., Eizenga, J. M., Guarracino, A., Paten, B., Garrison, E., & Moreto, M. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btad074 · Cited by 66
Kim, M. C., Lee, S., Park, J. K., Park, J., Lee, D., Park, J., Kim, B.-Y., Cho, M. S., Kim, T.-Y., Park, H. Y., et al. (2021) · Journal of Medicinal Food · doi:10.1089/jmf.2020.4746 · Cited by 18
Zolova, O. E., & Wight, P. A. (2011) · ASN Neuro · doi:10.1042/an20110021 · Cited by 15
(2023) · doi:10.1186/s13059-023-03008-6 · Cited by 4
Metadata
- Authors
- Myers, E. W., & Miller, W.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 1988
- Volume
- 4
- Issue
- 1
- Pages
- 11-17
- ISSN
- 0266-7061 (ISSN-L)
- 1367-4803
- 1460-2059
- OpenAlex
- W2108215151
- Cited by
- 1,235
- References
- 11
- FWCI
- 18.22
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.