The DOI matches its Crossref record; 64 of the 64 references it cites were found in a registry or an index.
Fast Statistical Alignment
Open accessAbstract
We describe a new program for the alignment of multiple biological sequences that is both statistically motivated and fast enough for problem sizes that arise in practice. Our Fast Statistical Alignment program is based on pair hidden Markov models which approximate an insertion/deletion process on a tree and uses a sequence annealing algorithm to combine the posterior probabilities estimated from these models into a multiple alignment. FSA uses its explicit statistical model to produce multiple alignments which are accompanied by estimates of the alignment accuracy and uncertainty for every column and character of the alignment--previously available only with alignment programs which use computationally-expensive Markov Chain Monte Carlo approaches--yet can align thousands of long sequences. Moreover, FSA utilizes an unsupervised query-specific learning procedure for parameter estimation which leads to improved accuracy on benchmark reference alignments in comparison to existing programs. The centroid alignment approach taken by FSA, in combination with its learning procedure, drastically reduces the amount of false-positive alignment on biological data in comparison to that given by other methods. The FSA program and a companion visualization tool for exploring uncertainty in alignments can be used via a web interface at http://orangutan.math.berkeley.edu/fsa/, and the source code is available at http://fsa.sourceforge.net/.
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
Clustal W and Clustal X version 2.0
Larkin, M. A., Blackshields, G., Brown, N. P., Chenna, R., McGettigan, P. A., McWilliam, H., Valentin, F., Wallace, I. M., Wilm, A., Lopez, R., et al. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm404 · Cited by 28,358
PHYLIP-Phylogeny inference package (Version 3.2)
Felsenstein, J. (1989) · Cladistics · Cited by 17,682
(1993) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040023 · Cited by 11,229
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
Greengenes, a Chimera-Checked 16S rRNA Gene Database and Workbench Compatible with ARB
DeSantis, T. Z., Hugenholtz, P., Larsen, N., Rojas, M., Brodie, E. L., Keller, K., Huber, T., Dalevi, D., Hu, P., & Andersen, G. L. (2006) · Applied and Environmental Microbiology · doi:10.1128/aem.03006-05 · Cited by 10,891
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
T-coffee: a novel method for fast and accurate multiple sequence alignment 1 1Edited by J. Thornton
Notredame, C., Higgins, D. G., & Heringa, J. (2000) · Journal of Molecular Biology · doi:10.1006/jmbi.2000.4042 · Cited by 6,852
Versatile and open software for comparing large genomes
Kurtz, S., Phillippy, A., Delcher, A. L., Smoot, M., Shumway, M., Antonescu, C., & Salzberg, S. L. (2004) · Genome Biology · doi:10.1186/gb-2004-5-2-r12 · Cited by 5,254
Self-citationRecent 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
Biological sequence analysis probabilistic models of proteins and nucleic acids
Durbin, R. M., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cited by 3,565
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
Automated generation of heuristics for biological sequence comparison
Slater, G. S. C., & Birney, E. (2005) · BMC Bioinformatics · doi:10.1186/1471-2105-6-31 · Cited by 2,933
Evolution of genes and genomes on the Drosophila phylogeny
Drosophila 12 Genomes Consortium (2007) · Nature · doi:10.1038/nature06341 · Cited by 2,010
Sequencing and comparison of yeast species to identify genes and regulatory elements
Kellis, M., Patterson, N., Endrizzi, M., Birren, B., & Lander, E. S. (2003) · Nature · doi:10.1038/nature01644 · Cited by 1,753
Rfam: annotating non-coding RNAs in complete genomes
Griffiths-Jones, S. (2004) · Nucleic Acids Research · doi:10.1093/nar/gki081 · Cited by 1,714
The Jalview Java alignment editor
Clamp, M., Cuff, J., Searle, S. M., & Barton, G. J. (2004) · Bioinformatics · doi:10.1093/bioinformatics/btg430 · Cited by 1,580
Aligning Multiple Genomic Sequences With the Threaded Blockset Aligner
Blanchette, M., Kent, W. J., Riemer, C., Elnitski, L., Smit, A. F. A., Roskin, K. M., Baertsch, R., Rosenbloom, K., Clawson, H., Green, E. D., et al. (2004) · Genome Research · doi:10.1101/gr.1933104 · Cited by 1,452
LAGAN and Multi-LAGAN: Efficient tools for large-scale multiple alignment of genomic DNA
Brudno, M., Do, C. B., Cooper, G. M., Kim, M. F., Davydov, E., Program, N. C. S., Green, E. D., Sidow, A., & Batzoglou, S. (2003) · Genome Research · doi:10.1101/gr.926603 · Cited by 1,115
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
Phylogeny-Aware Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis
Löytynoja, A., & Goldman, N. (2008) · Science · doi:10.1126/science.1158395 · Cited by 802
Multiple sequence alignment using partial order graphs
Lee, C., Grasso, C., & Sharlow, M. F. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.3.452 · Cited by 764
Direct evidence of extensive diversity of HIV-1 in Kinshasa by 1960
Worobey, M., Gemmel, M., Teuwen, D. E., Haselkorn, T., Kunstman, K., Bunce, M., Muyembe, J.-J., Kabongo, J.-M. M., Kalengayi, R. M., Van Marck, E., et al. (2008) · Nature · doi:10.1038/nature07390 · Cited by 650
Edgar, R. C., & Batzoglou, S. (2006) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2006.04.004 · Cited by 517
An evolutionary model for maximum likelihood alignment of DNA sequences
Thorne, J. L., Kishino, H., & Felsenstein, J. (1991) · Journal of Molecular Evolution · doi:10.1007/bf02193625 · Cited by 444
Alignment Uncertainty and Genomic Analysis
Wong, K. M., Suchard, M. A., & Huelsenbeck, J. P. (2008) · Science · doi:10.1126/science.1151532 · Cited by 411
BAliBASE 3.0: Latest developments of the multiple sequence alignment benchmark
Thompson, J. D., Koehl, P., Ripp, R., & Poch, O. (2005) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.20527 · Cited by 404
Allocating Independent Subtasks on Parallel Processors
Kruskal, C. P., & Weiss, A. A. (1985) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1985.231547 · Cited by 347
TeXshade: shading and labeling of multiple sequence alignments using LaTeX2e
Beitz, E. (2000) · Bioinformatics · doi:10.1093/bioinformatics/16.2.135 · Cited by 329
Multiple DNA and protein sequence alignment based on segment-to-segment comparison.
Morgenstern, B., Dress, A., & Werner, T. (1996) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.93.22.12098 · Cited by 299
Enredo and Pecan: Genome-wide mammalian consistency-based multiple alignment with paralogs
Paten, B., Herrero, J., Beal, K., Fitzgerald, S., & Birney, E. (2008) · Genome Research · doi:10.1101/gr.076554.108 · Cited by 291
MAVID: Constrained Ancestral Alignment of Multiple Sequences
Bray, N., & Pachter, L. (2004) · Genome Research · doi:10.1101/gr.1960404 · Cited by 284
Self-citationThe European ribosomal RNA database
Wuyts, J. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh065 · Cited by 263
BAli-Phy: simultaneous Bayesian inference of alignment and phylogeny
Suchard, M. A., & Redelings, B. D. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl175 · Cited by 243
SABmark—a benchmark for sequence alignment that covers the entire known fold space
Van Walle, I., Lasters, I., & Wyns, L. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bth493 · Cited by 230
DIALIGN-TX: greedy and progressive approaches for segment-based multiple sequence alignment
Subramanian, A. R., Kaufmann, M., & Morgenstern, B. (2008) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-3-6 · Cited by 229
Probalign: multiple sequence alignment using partition function posterior probabilities
Roshan, U., & Livesay, D. R. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl472 · Cited by 222
Viral Population Estimation Using Pyrosequencing
Eriksson, N., Pachter, L., Mitsuya, Y., Rhee, S.-Y., Wang, C., Gharizadeh, B., Ronaghi, M., Shafer, R. W., & Beerenwinkel, N. (2008) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000074 · Cited by 222
Self-citationUncertainty in homology inferences: Assessing and improving genomic sequence alignmentPreprint
Lunter, G. A., Rocco, A., Mimouni, N., Heger, A., Caldeira, A., & Hein, J. (2007) · Genome Research · doi:10.1101/gr.6725608 · Cited by 145
DNA assembly with gaps (Dawg): simulating sequence evolution
Cartwright, R. A. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1200 · Cited by 143
An enhanced RNA alignment benchmark for sequence alignment programs
Wilm, A., Mainz, I., & Steger, G. (2006) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-1-19 · Cited by 137
Comprehensive study on iterative algorithms of multiple sequence alignment
Hirosawa, M., Totoki, Y., Hoshida, M., & Ishikawa, M. (1995) · Computer applications in the biosciences · doi:10.1093/bioinformatics/11.1.13 · Cited by 133
Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints
Dowell, R. D., & Eddy, S. R. (2006) · BMC Bioinformatics · doi:10.1186/1471-2105-7-400 · Cited by 126
Pei, J., & Grishin, N. V. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkl514 · Cited by 125
Comparison of genomic DNA sequences: solved and unsolved problems
Miller, W. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.5.391 · Cited by 115
Hein, J., Wiuf, C., Knudsen, B., Möller, M., & Wibling, G. (2000) · Journal of Molecular Biology · doi:10.1006/jmbi.2000.4061 · Cited by 114
Dynamic Programming Alignment Accuracy
Holmes, I. H., & Durbin, R. M. (1998) · Journal of Computational Biology · doi:10.1089/cmb.1998.5.493 · Cited by 101
Self-citationA dynamic topological sort algorithm for directed acyclic graphs
Pearce, D. J., & Kelly, P. H. J. (2007) · ACM Journal of Experimental Algorithmics · doi:10.1145/1187436.1210590 · Cited by 95
Novák, Á., Miklós, I., Lyngsø, R. B., & Hein, J. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn457 · Cited by 91
Göttgens, B., Gilbert, J. G. R., Barton, L. M., Grafham, D. V., Rogers, J., Bentley, D., & Green, A. R. (2001) · Genome Research · doi:10.1101/gr.153001 · Cited by 88
Multiple alignment by sequence annealing
Schwartz, A. S., & Pachter, L. S. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btl311 · Cited by 86
Self-citationProbabilistic Phylogenetic Inference with Insertions and Deletions
Rivas, E., & Eddy, S. R. (2008) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000172 · Cited by 75
The CHAOS/DIALIGN WWW server for multiple alignment of genomic sequences
Brudno, M., Steinkamp, R., & Morgenstern, B. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh361 · Cited by 73
Sequence Alignments and Pair Hidden Markov Models Using Evolutionary History
Knudsen, B., & Miyamoto, M. M. (2003) · Journal of Molecular Biology · doi:10.1016/j.jmb.2003.08.015 · Cited by 69
Indel-Based Evolutionary Distance and Mouse–Human DivergencePreprint
Ogurtsov, A. Y., Sunyaev, S. R., & Kondrashov, A. S. (2004) · Genome Research · doi:10.1101/gr.2450504 · Cited by 60
Segment-based multiple sequence alignment
Rausch, T., Emde, A., Weese, D., Gogol‐Döring, A., Notredame, C., & Reinert, K. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn281 · Cited by 56
Chapman, M. A., Donaldson, I. J., Gilbert, J. G. R., Grafham, D. V., Rogers, J., Green, A. R., & Göttgens, B. (2004) · Genome Research · doi:10.1101/gr.1759004 · Cited by 53
MORPH: Probabilistic Alignment Combined with Hidden Markov Models of cis-Regulatory Modules
Sinha, S., & He, X. (2005) · PLoS Computational Biology · doi:10.1371/journal.pcbi.0030216 · Cited by 40
Tools for simulating evolution of aligned genomic regions with integrated parameter estimation
Varadarajan, A. V., Bradley, R. K., & Holmes, I. H. (2008) · Genome biology · doi:10.1186/gb-2008-9-10-r147 · Cited by 22
Self-citationAbdeddaïm, S., & Morgenstern, B. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45727-5_1 · Cited by 21
Studies in Probabilistic Sequence Alignment and Evolution
Holmes, I., Birney, E., Bruno, B., Durbin, R. M., Eddy, S. R., Haussler, D. H., Higgins, D. G., Hubbard, T., Krogh, A., Lawrence, C., et al. (1998) · Cited by 19
Self-citationWhole-genome alignments and polytopes for comparative genomics
Pachter, L. S., & Dewey, C. N. (2006) · Cited by 16
Self-citationPosterior decoding methods for optimization and accuracy control of multiple alignments
Pachter, L. S., & Schwartz, A. (2007) · Cited by 8
Self-citationWhole-Genome Alignments and Polytopes for Comparative Genomics
Dewey, C. N. (2006) · UC Berkeley · Cited by 4
Self-citation
Cited by
Fast, scalable generation of high‐quality protein multiple sequence alignments using Clustal Omega
Sievers, F., Wilm, A., Dineen, D., Gibson, T. J., Karplus, K., Li, W., Lopez, R., McWilliam, H., Remmert, M., Söding, J., et al. (2011) · Molecular Systems Biology · doi:10.1038/msb.2011.75 · Cited by 15,355
FastTree 2 – Approximately Maximum-Likelihood Trees for Large Alignments
Price, M. N., Dehal, P. S., & Arkin, A. P. (2010) · PLoS ONE · doi:10.1371/journal.pone.0009490 · Cited by 14,894
progressiveMauve: Multiple Genome Alignment with Gene Gain, Loss and Rearrangement
Darling, A. E., Mau, B., & Perna, N. T. (2010) · PLoS ONE · doi:10.1371/journal.pone.0011147 · Cited by 3,848
Cabili, M. N., Trapnell, C., Goff, L., Koziol, M., Tazon-Vega, B., Regev, A., & Rinn, J. L. (2011) · Genes & Development · doi:10.1101/gad.17446611 · Cited by 3,502
Detection of nonneutral substitution rates on mammalian phylogenies
Pollard, K. S., Hubisz, M. J., Rosenbloom, K. R., & Siepel, A. (2010) · Genome Research · doi:10.1101/gr.097857.109 · Cited by 2,353
Metadata
- Authors
- Bradley, R. K., Roberts, A., Smoot, M., Juvekar, S., Do, J., Dewey, C., Holmes, I., & Pachter, L.
- Venue
- PLoS Computational Biology
- Publisher
- Public Library of Science (PLoS)
- Published
- 2009-05-29
- Volume
- 5
- Issue
- 5
- Pages
- e1000392
- ISSN
- 1553-734X (ISSN-L)
- 1553-7358
- OpenAlex
- W2011289056
- Cited by
- 353
- References
- 64
- FWCI
- 12.60
- Type
- journal article
- Language
- en
- Open access
- gold
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.