The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
An algorithm for progressive multiple alignment of sequences with insertions
Open accessAbstract
Dynamic programming algorithms guarantee to find the optimal alignment between two sequences. For more than a few sequences, exact algorithms become computationally impractical, and progressive algorithms iterating pairwise alignments are widely used. These heuristic methods have a serious drawback because pairwise algorithms do not differentiate insertions from deletions and end up penalizing single insertion events multiple times. Such an unrealistically high penalty for insertions typically results in overmatching of sequences and an underestimation of the number of insertion events. We describe a modification of the traditional alignment algorithm that can distinguish insertion from deletion and avoid repeated penalization of insertions and illustrate this method with a pair hidden Markov model that uses an evolutionary scoring function. In comparison with a traditional progressive alignment method, our algorithm infers a greater number of insertion events and creates gaps that are phylogenetically consistent but spatially less concentrated. Our results suggest that some insertion/deletion “hot spots” may actually be artifacts of traditional alignment algorithms.
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
Thompson, J. D., Higgins, D. G., & Gibson, T. J. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.22.4673 · Cited by 64,617
MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform
Katoh, K. (2002) · Nucleic Acids Research · doi:10.1093/nar/gkf436 · Cited by 17,027
Evolutionary trees from DNA sequences: A maximum likelihood approach.
Felsenstein, J. (1981) · Journal of Molecular Evolution · doi:10.1007/bf01734359 · Cited by 14,571
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288
Evolution of Protein Molecules
JUKES, T. H., & CANTOR, C. R. (1969) · Mammalian Protein Metabolism · doi:10.1016/b978-1-4832-3211-9.50009-7 · Cited by 11,032
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
Dating of the human–ape splitting by a molecular clock of mitochondrial DNA.
Hasegawa, M., Kishino, H., & Yano, T.-A. (1985) · Journal of Molecular Evolution · doi:10.1007/bf02101694 · Cited by 8,687
Eddy, S. R. (1998) · Bioinformatics · doi:10.1093/bioinformatics/14.9.755 · Cited by 5,515
Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids
Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511790492 · Cited by 3,246
(1964) · Mammalian Protein Metabolism · doi:10.1016/b978-1-4832-3210-2.50006-6 · Cited by 3,059
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
Shukla, S., Mishra, B., Avashthi, H., & Chandra, M. (2022) · Bioinformatics · doi:10.1016/b978-0-323-89775-4.00003-1 · Cited by 1,244
Optimal alignments in linear space
Myers, E. W., & Miller, W. (1988) · Bioinformatics · doi:10.1093/bioinformatics/4.1.11 · Cited by 1,235
A linear space algorithm for computing maximal common subsequences
Hirschberg, D. S. (1975) · Communications of the ACM · doi:10.1145/360825.360861 · Cited by 1,093
A 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
Minimal Mutation Trees of Sequences
Sankoff, D. (1975) · SIAM Journal on Applied Mathematics · doi:10.1137/0128004 · Cited by 575
Molecular phylogenetics: state-of-the-art methods for looking into the past
Whelan, S., Liò, P., & Goldman, N. (2001) · Trends in Genetics · doi:10.1016/s0168-9525(01)02272-7 · Cited by 417
Self-citationThe alignment of sets of sequences and the construction of phyletic trees: An integrated method
Hogeweg, P., & Hesper, B. (1984) · Journal of Molecular Evolution · doi:10.1007/bf02257378 · Cited by 263
(1989) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040577 · Cited by 174
Research works printed but not linked: 5
- Levenshtein, V. I. (1966) Sov. Phys. Dokl. 10 , 707-710.
- 10.1093/bioinformatics/16.1.41 · doi:10.1093/bioinformatics/16.1.41
- Myers, E. W. & Miller, W. (1988) Comput. Appl. Biosci. 4 , 11-17.3382986
- Hein, J. (1989) Mol. Biol. Evol. 6 , 649-668.2488477
- Gonnet G. H. & Benner S. A. (1996) in Algorithm Theory: SWAT'96 eds. Karlsson R. & Lingas A. (Springer Berlin) pp. 380-391. · doi:10.1007/3-540-61422-2_147
Cited by
The ENCODE Project Consortium (2007) · Nature · doi:10.1038/nature05874 · Cited by 5,223
GENCODE: The reference human genome annotation for The ENCODE Project
Harrow, J., Frankish, A., Gonzalez, J. M., Tapanari, E., Diekhans, M., Kokocinski, F., Aken, B. L., Barrell, D., Zadissa, A., Searle, S., et al. (2012) · Genome Research · doi:10.1101/gr.135350.111 · Cited by 4,585
Whole-genome analyses resolve early branches in the tree of life of modern birds
Jarvis, E. D., Mirarab, S., Aberer, A. J., Li, B., Houde, P., Li, C., Ho, S. Y. W., Faircloth, B. C., Nabholz, B., Howard, J. T., et al. (2014) · Science · doi:10.1126/science.1253451 · Cited by 1,901
TranslatorX: multiple alignment of nucleotide sequences guided by amino acid translations
Abascal, F., Zardoya, R., & Telford, M. J. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkq291 · Cited by 1,486
Hedgehog: functions and mechanisms
Varjosalo, M., & Taipale, J. (2008) · Genes & Development · doi:10.1101/gad.1693608 · Cited by 1,217
Metadata
- Authors
- Löytynoja, A., & Goldman, N.
- Venue
- Proceedings of the National Academy of Sciences
- Publisher
- National Academy of Sciences
- Published
- 2005-07-06
- Volume
- 102
- Issue
- 30
- Pages
- 10557-10562
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W1646393397
- Cited by
- 907
- References
- 19
- FWCI
- 4.72
- Type
- journal article
- Language
- en
- Open access
- green
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.