Murasaki: A Fast, Parallelizable Algorithm to Find Anchors from Multiple Genomes
Open accessAbstract
BACKGROUND: With the number of available genome sequences increasing rapidly, the magnitude of sequence data required for multiple-genome analyses is a challenging problem. When large-scale rearrangements break the collinearity of gene orders among genomes, genome comparison algorithms must first identify sets of short well-conserved sequences present in each genome, termed anchors. Previously, anchor identification among multiple genomes has been achieved using pairwise alignment tools like BLASTZ through progressive alignment tools like TBA, but the computational requirements for sequence comparisons of multiple genomes quickly becomes a limiting factor as the number and scale of genomes grows. METHODOLOGY/PRINCIPAL FINDINGS: Our algorithm, named Murasaki, makes it possible to identify anchors within multiple large sequences on the scale of several hundred megabases in few minutes using a single CPU. Two advanced features of Murasaki are (1) adaptive hash function generation, which enables efficient use of arbitrary mismatch patterns (spaced seeds) and therefore the comparison of multiple mammalian genomes in a practical amount of computation time, and (2) parallelizable execution that decreases the required wall-clock and CPU times. Murasaki can perform a sensitive anchoring of eight mammalian genomes (human, chimp, rhesus, orangutan, mouse, rat, dog, and cow) in 21 hours CPU time (42 minutes wall time). This is the first single-pass in-core anchoring of multiple mammalian genomes. We evaluated Murasaki by comparing it with the genome alignment programs BLASTZ and TBA. We show that Murasaki can anchor multiple genomes in near linear time, compared to the quadratic time requirements of BLASTZ and TBA, while improving overall accuracy. CONCLUSIONS/SIGNIFICANCE: Murasaki provides an open source platform to take advantage of long patterns, cluster computing, and novel hash algorithms to produce accurate anchors across multiple genomes with computational efficiency significantly greater than existing methods. Murasaki is available under GPL at http://murasaki.sourceforge.net.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Mauve may have limitations in handling extremely large genomes or genomes with high levels of divergence.
“However, it may have limitations in handling extremely large genomes or genomes with high levels of divergence.”
From Whole-Genome Alignment: Methods, Challenges, and Future Directions (2024) · cites this paper as [31]
The Discussion’s “Choice of comparison algorithm” section says Mauve is well suited to bacterial genomes but not well suited to mammalian-scale genomes, supporting the large-genome limitation. It does not say that Mauve has limitations with highly divergent genomes. (LLM, conf=0.85)
Experimental — accuracy not yet measuredBLASTZ uses chaining to link multiple short alignments into longer, contiguous alignments, which helps identify regions of similarity even in the presence of genomic rearrangements.
“It uses a strategy called 'chaining' to link multiple short alignments into longer, contiguous alignments, which helps identify regions of similarity even in the presence of genomic rearrangements [31].”
From Whole-Genome Alignment: Methods, Challenges, and Future Directions (2024) · cites this paper as [31]
Results > Experiment Design (page unavailable) says BLASTZ has a chaining step, though the authors disabled it to obtain short high-scoring pairs. The Background (page unavailable) connects BLASTZ-based anchor identification with comparisons involving genomic rearrangements. Our copy does not say that BLASTZ’s chaining links short alignments into longer contiguous alignments or that chaining itself helps identify similarity despite rearrangements. (LLM, conf=0.82)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 29
- [1]Smith TF Waterman MS 1981 Identification of common molecular subsequences. Journal of Molecular Biology 147 195 197 7265238
- [2]Pearson Lipman 1988 Improved tools for biological sequence comparison. 24444 24448 In: Proc. Natl. Acad. Sci. volume 85 PMC280013 3162770
- [3]Altschul SF Gish W Miller W Myers EW Lipman DJ 1990 Basic local alignment search tool. J Mol Biol 215 403 410 2231712
- [4]Darling AC Mau B Blattner FR Perna NT 2004 Mauve: Multiple Alignment of Conserved Genomic Sequence With Rearrangements. Genome Res 14 1394 1403 15231754 PMC442156
- [5]Brudno M Do CB Cooper GM Kim MF Davydov E 2003 LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA. Genome Res 13 721 731 12654723 PMC430158
- [6]Bourque G Pevzner PA 2002 Genome-Scale Evolution: Reconstructing Gene Orders in the Ancestral Species. Genome Res 12 26 36 11779828 PMC155248
- [7]Bejerano G Pheasant M Makunin I Stephen S Kent WJ 2004 Ultraconserved Elements in the Human Genome. Science 304 1321 1325 15131266
- [8]Delcher A Kasif S Fleischmann R Peterson J White O 1999 Alignment of whole genomes. Nucl Acids Res 27 2369 2376 10325427 PMC148804
- [9]Ohlebusch E Kurtz S 2008 Space efficient computation of rare maximal exact matches between multiple sequences. J Comput Biol 15 357 377 18361760
- [10]Schwartz S Kent WJ Smit A Zhang Z Baertsch R 2003 Human-Mouse Alignments with BLASTZ. Genome Res 13 103 107 12529312 PMC430961
- [11]Ma B Tromp J Li M 2002 Patternhunter: faster and more sensitive homology search. Bioinformatics 18 440 445 11934743
- [12]Preparata FP Zhang L Choi KW 2005 Quick, practical selection of effective seeds for homology search. J Computational Biology 12 1137 1152 16305325
- [13]Tabus I Korodi G 2008 Genome compression using normalized maximum likelihood models for constrained markov sources. 261 265 In: Information Theory Workshop, 2008. ITW '08. IEEE doi: 10.1109/ITW.2008.4578663 · DOI
- [14]Farach M Noordewier M Savari S Shepp L Wyner A 1995 On the entropy of dna: algorithms and measurements based on memory and rapid convergence. SODA '95: Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms Philadelphia, PA Society for Industrial and Applied Mathematics 48 57
- [18]Waterston RH Lindblad-Toh K Birney E Rogers J Abril JF 2002 Initial sequencing and comparative analysis of the mouse genome. Nature 420 520 562 12466850
- [19]Dewey CN Huggins PM Woods K Sturmfels B Pachter L 2006 Parametric alignment of Drosophila genomes. PLoS Comput Biol 2 e73 16789815 PMC1480539
- [20]Gibbs RA Weinstock GM Metzker ML Muzny DM Sodergren EJ 2004 Genome sequence of the brown norway rat yields insights into mammalian evolution. Nature 428 493 521 15057822
- [21]Hachiya T Osana Y Popendorf K Sakakibara Y 2009 Accurate identification of orthologous segments among multiple genomes. Bioinformatics 25 853 860 19188192
- [22]Blanchette M Kent WJ Riemer C Elnitski L Smit AF 2004 Aligning Multiple Genomic Sequences With the Threaded Blockset Aligner. Genome Research 14 708 715 15060014 PMC383317
- [23]Miller W Rosenbloom K Hardison RC Hou M Taylor J 2007 28-way vertebrate alignment and conservation track in the UCSC Genome Browser. Genome Res 17 1797 1808 17984227 PMC2099589
- [24]Liolios K Mavromatis K Tavernarakis N Kyrpides NC 2008 The Genomes On Line Database (GOLD) in 2007: status of genomic and metagenomic projects and their associated metadata. Nucleic Acids Res 36 D475 479 17981842 PMC2238992
- [25]Kemena C Notredame C 2009 Upcoming challenges for multiple sequence alignment methods in the high-throughput era. Bioinformatics 25 2455 2465 19648142 PMC2752613
- [26]Kish LB 2002 End of moore's law: thermal (noise) death of integration in micro and nano electronics. Physics Letters A 305 144 149
- [27]Bentley DR Balasubramanian S Swerdlow HP Smith GP Milton J 2008 Accurate whole human genome sequencing using reversible terminator chemistry. Nature 456 53 59 18987734 PMC2581791
- [28]Simpson JT Wong K Jackman SD Schein JE Jones SJ 2009 ABySS: A parallel assembler for short read sequence data. Genome Research 19 1117 1123 19251739 PMC2694472
- [29]Mathee K Narasimhan G Valdes C Qiu X Matewish JM 2008 Dynamics of Pseudomonas aeruginosa genome evolution. Proceedings of the National Academy of Sciences 105 3100 3105 PMC2268591 18287045
- [31]Hubbard T Barker D Birney E Cameron G Chen Y 2002 The Ensembl genome database project. Nucl Acids Res 30 38 41 11752248 PMC99161
- [32]Vallender EJ Paschall JE Malcom CM Lahn BT Wyckoff GJ 2006 SPEED: a molecular-evolution-based database of mammalian orthologous groups. Bioinformatics 22 2835 2837 16966361
- [33]Pevzner P Tesler G 2003 Genome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse Genomes. Genome Res 13 37 45 12529304 PMC430962
Cited by
Sorted by citations
Whole-Genome Alignment: Methods, Challenges, and Future Directions
Saada, B., Zhang, T., Siga, E., Zhang, J., & Magalhães Muniz, M. M. (2024) · Applied Sciences · doi:10.3390/app14114837 · Cited by 15 · see citing works
- Authors
- Popendorf, K., Tsuyoshi, H., Osana, Y., & Sakakibara, Y.
- Affiliations
- Keio University (JP)
- Seikei University (JP)
- Corresponding author
- Sakakibara, Yasubumi
- Venue
- PLoS ONE
- Publisher
- Public Library of Science (PLoS)
- Published
- 2010-09-24
- Volume
- 5
- Issue
- 9
- Pages
- e12651
- ISSN
- 1932-6203 (ISSN-L)
- PMC
- PMC2945767
- OpenAlex
- W2049518666
- Cited by
- 32
- References
- 0
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 1 · 2023: 1 · 2021: 3 · 2020: 1 · 2019: 1 · 2018: 6 · 2017: 1 · 2016: 1 · 2015: 6 · 2014: 3 · 2013: 2 · 2012: 2
- FWCI
- 0.83
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- PLoS ONE (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- Figshare (submittedVersion, cc-by)
- Funders
- Takeda Science Foundation
- Keio University
- Japan Society for the Promotion of Science (17018029)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Keywords
- spaced seeds, parallelizable algorithms, mammalian genomes, genome rearrangement, TBA
- MeSH terms
- Algorithms, Animals, Bacteria, Cattle, Dogs, Humans, Mammals, Sequence Alignment, Genome, Conserved Sequence, Mice, Rats
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
