The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Multiple sequence alignment using partial order graphs
Abstract
Motivation: Progressive Multiple Sequence Alignment (MSA) methods depend on reducing an MSA to a linear profile for each alignment step. However, this leads to loss of information needed for accurate alignment, and gap scoring artifacts. Results: We present a graph representation of an MSA that can itself be aligned directly by pairwise dynamic programming, eliminating the need to reduce the MSA to a profile. This enables our algorithm (Partial Order Alignment (POA)) to guarantee that the optimal alignment of each new sequence versus each sequence in the MSA will be considered. Moreover, this algorithm introduces a new edit operator, homologous recombination, important for multidomain sequences. The algorithm has improved speed (linear time complexity) over existing MSA algorithms, enabling construction of massive and complex alignments (e.g. an alignment of 5000 sequences in 4 h on a Pentium II). We demonstrate the utility of this algorithm on a family of multidomain SH2 proteins, and on EST assemblies containing alternative splicing and polymorphism. Availability: The partial order alignment program POA is available at http://www.bioinformatics.ucla.edu/poa. Contact: leec@mbi.ucla.edu * To whom correspondence should be addressed. 2 Current address: center for Applied Mathematics, 657 Rhodes Hall, Cornell University, Ithaca NY 14853, USA.
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
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 · cited 7×
“This strategy was implemented in CLUSTALW, which has been one of the most commonly used MSA programs since 1994 (Thompson et al., 1994).”
BackgroundMethodInfluentialNeedleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288
Identification of common molecular subsequences
Smith, T. F., & Waterman, M. S. (1981) · Journal of Molecular Biology · doi:10.1016/0022-2836(81)90087-5 · Cited by 9,940
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
CLUSTAL: a package for performing multiple sequence alignment on a microcomputer
Higgins, D. G., & Sharp, P. M. (1988) · Gene · doi:10.1016/0378-1119(88)90330-7 · Cited by 3,394
[5] Rapid and sensitive sequence comparison with FASTP and FASTA
Pearson, W. R. (1990) · Methods in Enzymology · doi:10.1016/0076-6879(90)83007-v · Cited by 1,946
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
Eddy, S. R. (1996) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(96)80056-x · Cited by 1,430
Genome-wide detection of alternative splicing in expressed sequences of human genes
Modrek, B. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.13.2850 · Cited by 679
Cited by
Velvet: Algorithms for de novo short read assembly using de Bruijn graphs
Zerbino, D. R., & Birney, E. (2008) · Genome Research · doi:10.1101/gr.074492.107 · Cited by 9,491
Pruesse, E., Quast, C., Knittel, K., Fuchs, B. M., Ludwig, W., Peplies, J., & Glockner, F. O. (2007) · Nucleic Acids Research · doi:10.1093/nar/gkm864 · Cited by 6,668
Mauve: Multiple alignment of conserved genomic sequence with rearrangements
Darling, A. C. E., Mau, B., Blattner, F. R., & Perna, N. T. (2004) · Genome Research · doi:10.1101/gr.2289704 · Cited by 4,949
“…can be readily observed between both closely related and divergent organisms of all types (Tillier and Collins 2000; Eichler and 2 similar to Smith-Waterman and Needleman-Wunsch (Thompson et al. 1994; Morgenstern et al. 1996; Morgenstern 1999; Notre-dame et al. 2000; Lee et al. 2002).”
BackgroundNonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data
Chin, C.-S., Alexander, D. H., Marks, P., Klammer, A. A., Drake, J., Heiner, C., Clum, A., Copeland, A., Huddleston, J., Eichler, E. E., et al. (2013) · Nature Methods · doi:10.1038/nmeth.2474 · Cited by 4,029
SINA: Accurate high-throughput multiple sequence alignment of ribosomal RNA genes
Pruesse, E., Peplies, J., & Glöckner, F. O. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts252 · Cited by 3,079
Fast and accurate de novo genome assembly from long uncorrected reads
Vaser, R., Sović, I., Nagarajan, N., & Šikić, M. (2017) · Genome Research · doi:10.1101/gr.214270.116 · Cited by 3,043
Auch, A. F., von Jan, M., Klenk, H.-P., & Göker, M. (2010) · Standards in Genomic Sciences · doi:10.4056/sigs.531120 · Cited by 1,757
The Oxford Nanopore MinION: delivery of nanopore sequencing to the genomics community
Jain, M., Olsen, H. E., Paten, B., & Akeson, M. (2016) · Genome Biology · doi:10.1186/s13059-016-1103-0 · Cited by 1,588
“Their pipeline, ‘nanocorrect’, corrected errors by first aligning reads using the graphbased, greedy partial order aligner method [52], and then by pruning errors that were apparent given the alignment graph.”
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
Fast and accurate long-read assembly with wtdbg2
Ruan, J., & Li, H. (2020) · Nature Methods · doi:10.1038/s41592-019-0669-3 · Cited by 1,380
A complete bacterial genome assembled de novo using only nanopore sequencing data
Loman, N. J., Quick, J., & Simpson, J. T. (2015) · Nature Methods · doi:10.1038/nmeth.3444 · Cited by 1,294
A draft human pangenome reference.
Liao, W.-W., Asri, M., Ebler, J., Doerr, D., Haukness, M., Hickey, G., Lu, S., Lucas, J. K., Monlong, J., Abel, H. J., et al. (2023) · Nature · doi:10.1038/s41586-023-05896-x · Cited by 1,129
“For smoothxg, our first iteration attempts to generate 13033bp-long POA problems, while the second is 13177bp.”
MethodInfluential25 years of serving the community with ribosomal RNA gene reference databases and tools
Glöckner, F. O., Yilmaz, P., Quast, C., Gerken, J., Beccati, A., Ciuprina, A., Bruns, G., Yarza, P., Peplies, J., Westram, R., et al. (2017) · Journal of Biotechnology · doi:10.1016/j.jbiotec.2017.06.1198 · Cited by 947
Variation graph toolkit improves read mapping by representing genetic variation in the reference
Garrison, E., Sirén, J., Novak, A. M., Hickey, G., Eizenga, J. M., Dawson, E. T., Jones, W., Garg, S., Markello, C., Lin, M. F., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4227 · Cited by 821
Oxford Nanopore MinION Sequencing and Genome Assembly
Lu, H., Giordano, F., & Ning, Z. (2016) · Genomics, Proteomics & Bioinformatics · doi:10.1016/j.gpb.2016.05.004 · Cited by 935
Assembling large genomes with single-molecule sequencing and locality-sensitive hashing
Berlin, K., Koren, S., Chin, C.-S., Drake, J. P., Landolin, J. M., & Phillippy, A. M. (2015) · Nature Biotechnology · doi:10.1038/nbt.3238 · Cited by 934
MUSTANG: A multiple structural alignment algorithm
Konagurthu, A. S., Whisstock, J. C., Stuckey, P. J., & Lesk, A. M. (2006) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.20921 · Cited by 713
MIPS: analysis and annotation of proteins from whole genomes
Mewes, H. W. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh092 · Cited by 713
Kalign – an accurate and fast multiple sequence alignment algorithm
Lassmann, T., & Sonnhammer, E. L. (2005) · BMC Bioinformatics · doi:10.1186/1471-2105-6-298 · Cited by 705
From squiggle to basepair: computational approaches for improving nanopore sequencing read accuracy
Rang, F. J., Kloosterman, W. P., & de Ridder, J. (2018) · Genome Biology · doi:10.1186/s13059-018-1462-9 · Cited by 672
hybrid SPA des: an algorithm for hybrid assembly of short and long reads
Antipov, D., Korobeynikov, A., McLean, J. S., & Pevzner, P. A. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btv688 · Cited by 659
M-Coffee: combining multiple sequence alignment methods with T-Coffee
Wallace, I. M. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkl091 · Cited by 581
Nanopore sequencing and the Shasta toolkit enable efficient de novo assembly of eleven human genomes
Shafin, K., Pesout, T., Lorig-Roach, R., Haukness, M., Olsen, H. E., Bosworth, C., Armstrong, J., Tigyi, K., Maurer, N., Koren, S., et al. (2020) · Nature Biotechnology · doi:10.1038/s41587-020-0503-6 · Cited by 567
Modrek, B., & Lee, C. J. (2003) · Nature Genetics · doi:10.1038/ng1159 · Cited by 522
Self-citationEdgar, R. C., & Batzoglou, S. (2006) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2006.04.004 · Cited by 517
The design and construction of reference pangenome graphs with minigraph
Li, H., Feng, X., & Chu, C. (2020) · Genome Biology · doi:10.1186/s13059-020-02168-z · Cited by 455
Byrne, A., Beaudin, A. E., Olsen, H. E., Jain, M., Cole, C., Palmer, T., DuBois, R. M., Forsberg, E. C., Akeson, M., & Vollmers, C. (2017) · Nature Communications · doi:10.1038/ncomms16027 · Cited by 379
NextDenovo: an efficient error correction and accurate assembly tool for noisy long reads
Hu, J., Wang, Z., Sun, Z., Hu, B., Ayoola, A. O., Liang, F., Li, J., Sandoval, J. R., Cooper, D. N., Ye, K., et al. (2024) · Genome Biology · doi:10.1186/s13059-024-03252-4 · Cited by 431
ExpansionHunter: a sequence-graph-based tool to analyze variation in short tandem repeat regions
Dolzhenko, E., Deshpande, V., Schlesinger, F., Krusche, P., Petrovski, R., Chen, S., Emig-Agius, D., Gross, A., Narzisi, G., Bowman, B., et al. (2019) · Bioinformatics · doi:10.1093/bioinformatics/btz431 · Cited by 394
Genome graphs and the evolution of genome inference
Paten, B., Novak, A. M., Eizenga, J. M., & Garrison, E. (2017) · Genome Research · doi:10.1101/gr.214155.116 · Cited by 351
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
Assembly of long error-prone reads using de Bruijn graphs
Lin, Y., Yuan, J., Kolmogorov, M., Shen, M. W., Chaisson, M., & Pevzner, P. A. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1604560113 · Cited by 382
Eizenga, J. M., Novak, A. M., Sibbesen, J. A., Heumos, S., Ghaffaari, A., Hickey, G., Chang, X., Seaman, J. D., Rounthwaite, R., Ebler, J., et al. (2020) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-120219-080406 · Cited by 320
Comparing sequences without using alignments: application to HIV/SIV subtyping
Didier, G., Debomy, L., Pupin, M., Zhang, M., Grossmann, A., Devauchelle, C., & Laprevotte, I. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-1 · Cited by 362
Bradley, R. K., Roberts, A., Smoot, M., Juvekar, S., Do, J., Dewey, C., Holmes, I., & Pachter, L. (2009) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000392 · Cited by 353
Pangenome graph construction from genome alignments with Minigraph-Cactus
Hickey, G., Monlong, J., Ebler, J., Novak, A. M., Eizenga, J. M., Gao, Y., Human Pangenome Reference Consortium, Abel, H. J., Antonacci-Fulton, L. L., Asri, M., et al. (2024) · Nature Biotechnology · doi:10.1038/s41587-023-01793-w · Cited by 343
Duarte, J. M., Cui, L., Wall, P. K., Zhang, Q., Zhang, X., Leebens-Mack, J., Ma, H., Altman, N., & dePamphilis, C. W. (2006) · Molecular Biology and Evolution · doi:10.1093/molbev/msj051 · Cited by 339
3DCoffee: Combining Protein Sequences and Structures within Multiple Sequence Alignments
O'Sullivan, O., Suhre, K., Abergel, C., Higgins, D. G., & Notredame, C. (2004) · Journal of Molecular Biology · doi:10.1016/j.jmb.2004.04.058 · Cited by 318
Unsupervised Learning from Narrated Instruction Videos
Alayrac, J.-B., Bojanowski, P., Agrawal, N., Sivic, J., Laptev, I., & Lacoste-Julien, S. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.495 · Cited by 278
Garrison, E., Guarracino, A., Heumos, S., Villani, F., Bao, Z., Tattini, L., Hagmann, J., Vorbrugg, S., Marco-Sola, S., Kubica, C., et al. (2024) · Nature Methods · doi:10.1038/s41592-024-02430-3 · Cited by 277
A benchmark of multiple sequence alignment programs upon structural RNAs
Gardner, P. P. (2005) · Nucleic Acids Research · doi:10.1093/nar/gki541 · Cited by 273
Cactus: Algorithms for genome multiple sequence alignment
Paten, B., Earl, D., Nguyen, N., Diekhans, M., Zerbino, D., & Haussler, D. (2011) · Genome Research · doi:10.1101/gr.123356.111 · Cited by 243
Thompson, J. D., Linard, B., Lecompte, O., & Poch, O. (2011) · PLoS ONE · doi:10.1371/journal.pone.0018093 · Cited by 242
“A number of specific MSA problems have also been addressed by programs such as POA [28] for the alignment of non-linear sequences or PRANK [10] for the detailed evolutionary analysis of more closely related sequences.”
BackgroundGraphAligner: rapid and versatile sequence-to-graph alignment
Rautiainen, M., & Marschall, T. (2020) · Genome Biology · doi:10.1186/s13059-020-02157-2 · Cited by 242
High throughput error corrected Nanopore single cell transcriptome sequencing
Lebrigand, K., Magnone, V., Barbry, P., & Waldmann, R. (2020) · Nature Communications · doi:10.1038/s41467-020-17800-6 · Cited by 236
Cactus Graphs for Genome Comparisons
Paten, B., Diekhans, M., Earl, D., John, J. S., Ma, J., Suh, B., & Haussler, D. (2011) · Journal of Computational Biology · doi:10.1089/cmb.2010.0252 · Cited by 102
Garrison, E., & Guarracino, A. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btac743 · Cited by 95
Haplotype-aware pantranscriptome analyses using spliced pangenome graphs
Sibbesen, J. A., Eizenga, J. M., Novak, A. M., Sirén, J., Chang, X., Garrison, E., & Paten, B. (2023) · Nature Methods · doi:10.1038/s41592-022-01731-9 · Cited by 83
Issues in bioinformatics benchmarking: the case study of multiple sequence alignment
Aniba, M. R., Poch, O., & Thompson, J. D. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkq625 · Cited by 72
Foley, G., Mora, A., Ross, C. M., Bottoms, S., Sützl, L., Lamprecht, M. L., Zaugg, J., Essebier, A., Balderson, B., Newell, R., et al. (2022) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1010633 · Cited by 70
Pangenome Graph Construction from Genome Alignment with Minigraph-Cactus
Hickey, G., Monlong, J., Ebler, J., Novak, A., Eizenga, J. M., Gao, Y., Human Pangenome Reference Consortium, Marschall, T., Li, H., & Paten, B. (2022) · doi:10.1101/2022.10.06.511217 · Cited by 345
Metadata
- Authors
- Lee, C., Grasso, C., & Sharlow, M. F.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2002-03-01
- Volume
- 18
- Issue
- 3
- Pages
- 452-464
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2142113273
- Cited by
- 764
- References
- 25
- FWCI
- 7.88
- 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.