Optimal alignment between groups of sequences and its application to multiple sequence alignment
Open accessThe DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
Four algorithms, A-D, were developed to align two groups of biological sequences. Algorithm A is equivalent to the conventional dynamic programming method widely used for aligning ordinary sequences, whereas algorithms B-D are designed to evaluate the cost for a deletion/insertion more accurately when internal gaps are present in either or both groups of sequences. Rigorous optimization of the 'sum of pairs' (SP) score is achieved by algorithm D, whose average performance is close to O(MNL2), where M and N are numbers of sequences included in the two groups and L is the mean length of the sequences. Algorithm B uses some approximations to cope with profile-based operations, whereas algorithm C is a simpler variant of algorithm D. These group-to-group alignment algorithms were applied to multiple sequence alignment with two iterative strategies: a progressive method based on a given binary tree and a randomized grouping--realignment method. The advantages and disadvantages of the four algorithms are discussed on the basis of the results of examinations of several protein families.
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
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288 · cited 1×
“All the algorithms follow the dynamic programming paradigm (Needleman and Wunsch, 1970) formulated by Waterman et al. (1976) and improved in efficiency by Gotoh (1982).”
Progressive sequence alignment as a prerequisitetto correct phylogenetic trees
Feng, D.-F., & Doolittle, R. F. (1987) · Journal of Molecular Evolution · doi:10.1007/bf02603120 · Cited by 1,883
Profile analysis: detection of distantly related proteins.
Gribskov, M., McLachlan, A. D., & Eisenberg, D. (1987) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.84.13.4355 · Cited by 1,325
Cited by
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 Multiple Sequence Alignment Software Version 7: Improvements in Performance and Usability
Katoh, K., & Standley, D. M. (2013) · Molecular Biology and Evolution · doi:10.1093/molbev/mst010 · Cited by 46,209
“As listed in table 1, MAFFT version 7 has options for various alignment strategies, including progressive methods (PartTree, FFT-NS-1, and L-INS-1) (Feng and Doolittle 1987; Higgins and Sharp 1988; Katoh and Toh 2007), iterative refinement methods (FFT-NS-i, L-INS-i, E-INS-i, and G-INS-i) (Barton and Sternberg 1987; Be…”
MethodInfluentialMAFFT: 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
“To overcome this difficulty, various heuristic methods, including progressive methods (3) and iterative refinement methods (4–6), have been proposed to date.”
MethodMAFFT online service: multiple sequence alignment, interactive sequence choice and visualization
Katoh, K., Rozewicki, J., & Yamada, K. D. (2019) · Briefings in Bioinformatics · doi:10.1093/bib/bbx108 · Cited by 8,909
MAFFT version 5: improvement in accuracy of multiple sequence alignment
Katoh, K. (2005) · Nucleic Acids Research · doi:10.1093/nar/gki198 · Cited by 4,837
Metadata
- Authors
- Gotoh, O.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 1993
- Volume
- 9
- Issue
- 3
- Pages
- 361-370
- ISSN
- 0266-7061 (ISSN-L)
- 1367-4803
- 1460-2059
- OpenAlex
- W2068083406
- Cited by
- 127
- References
- 3
- FWCI
- 1.37
- Type
- journal article
- Language
- en
- Open access
- bronze
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.