| 1. |
- Cáceres, Manuel, et al.
(author)
-
Safety in Multi-Assembly via Paths Appearing in All Path Covers of a DAG
- 2022
-
In: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - : Institute of Electrical and Electronics Engineers (IEEE). - 1545-5963 .- 1557-9964 .- 2374-0043. ; 19:6, s. 3673-3684
-
Journal article (peer-reviewed)abstract
- A multi-assembly problem asks to reconstruct multiple genomic sequences from mixed reads sequenced from all of them. Standard formulations of such problems model a solution as a path cover in a directed acyclic graph, namely a set of paths that together cover all vertices of the graph. Since multi-assembly problems admit multiple solutions in practice, we consider an approach commonly used in standard genome assembly: output only partial solutions ( contigs , or safe paths ), that appear in all path cover solutions. We study constrained path covers, a restriction on the path cover solution that incorporate practical constraints arising in multi-assembly problems. We give efficient algorithms finding all maximal safe paths for constrained path covers. We compute the safe paths of splicing graphs constructed from transcript annotations of different species. Our algorithms run in less than 15 seconds per species and report RNA contigs that are over 99% precise and are up to 8 times longer than unitigs. Moreover, RNA contigs cover over 70% of the transcripts and their coding sequences in most cases. With their increased length to unitigs, high precision, and fast construction time, maximal safe paths can provide a better base set of sequences for transcript assembly programs.
|
|
| 2. |
|
|
| 3. |
- Crona, Mikael, et al.
(author)
-
NrdH-Redoxin Protein Mediates High Enzyme Activity in Manganese-reconstituted Ribonucleotide Reductase from Bacillus anthracis
- 2011
-
In: Journal of Biological Chemistry. - Bethesda, Md. : American Society for Biochemistry and Molecular Biology. - 0021-9258 .- 1083-351X. ; 286:38, s. 33053-33060
-
Journal article (peer-reviewed)abstract
- Bacillus anthracis is a severe mammalian pathogen encoding a class Ib ribonucleotide reductase (RNR). RNR is a universal enzyme that provides the four essential deoxyribonucleotides needed for DNA replication and repair. Almost all Bacillus spp. encode both class Ib and class III RNR operons, but the B. anthracis class III operon was reported to encode a pseudogene, and conceivably class Ib RNR is necessary for spore germination and proliferation of B. anthracis upon infection. The class Ib RNR operon in B. anthracis encodes genes for the catalytic NrdE protein, the tyrosyl radical metalloprotein NrdF, and the flavodoxin protein NrdI. The tyrosyl radical in NrdF is stabilized by an adjacent Mn(2)(III) site (Mn-NrdF) formed by the action of the NrdI protein or by a Fe(2)(III) site (Fe-NrdF) formed spontaneously from Fe(2+) and O(2). In this study, we show that the properties of B. anthracis Mn-NrdF and Fe-NrdF are in general similar for interaction with NrdE and NrdI. Intriguingly, the enzyme activity of Mn-NrdF was approximately an order of magnitude higher than that of Fe-NrdF in the presence of the class Ib-specific physiological reductant NrdH, strongly suggesting that the Mn-NrdF form is important in the life cycle of B. anthracis. Whether the Fe-NrdF form only exists in vitro or whether the NrdF protein in B. anthracis is a true cambialistic enzyme that can work with either manganese or iron remains to be established.
|
|
| 4. |
- Ekim, Baris, et al.
(author)
-
Efficient mapping of accurate long reads in minimizer space with mapquik
- 2023
-
In: Genome Research. - 1088-9051 .- 1549-5469. ; 33:7, s. 1188-1197
-
Journal article (peer-reviewed)abstract
- DNA sequencing data continue to progress toward longer reads with increasingly lower sequencing error rates. We focus on the critical problem of mapping, or aligning, low-divergence sequences from long reads (e.g., Pacific Biosciences [PacBio] HiFi) to a reference genome, which poses challenges in terms of accuracy and computational resources when using cutting-edge read mapping approaches that are designed for all types of alignments. A natural idea would be to optimize efficiency with longer seeds to reduce the probability of extraneous matches; however, contiguous exact seeds quickly reach a sensitivity limit. We introduce mapquik, a novel strategy that creates accurate longer seeds by anchoring alignments through matches of k consecutively sampled minimizers (k-min-mers) and only indexing k-min-mers that occur once in the reference genome, thereby unlocking ultrafast mapping while retaining high sensitivity. We show that mapquik significantly accelerates the seeding and chaining steps-fundamental bottlenecks to read mapping-for both the human and maize genomes with >96% sensitivity and near-perfect specificity. On the human genome, for both real and simulated reads, mapquik achieves a 37x speedup over the state-of-the-art tool minimap2, and on the maize genome, mapquik achieves a 410x speedup over minimap2, making mapquik the fastest mapper to date. These accelerations are enabled from not only minimizer-space seeding but also a novel heuristic O(n) pseudochaining algorithm, which improves upon the long-standing O(nlogn) bound. Minimizer-space computation builds the foundation for achieving real-time analysis of long-read sequencing data.
|
|
| 5. |
- Höhna, Sebastian, 1983-, et al.
(author)
-
Burnin Estimation and Convergence Assessment
-
Other publication (other academic/artistic)abstract
- Estimating the burnin length and assessing convergence purely from the output of an MCMC run is increasingly important in Bayesian phylogenetic inference. Previously, methods for estimating the burnin and assessing convergence have been ad-hoc, such as the minimum number of effective samples or the deviation in split frequencies. In this paper we compare the currently used methods to convergence assessment methods from the mathematical literature, namely the Geweke test and the Heidelberger-Welch test. The latter two show strong advantages in being statistically consistent and unbiased. Statistical consistency and unbiasedness was verified on simulated data with known posterior distributions. Both methods consider convergence as the Null hypothesis. The Null hypothesis is rejected based on standard p-values, which are easier to interpret than a threshold as used by the eeffective sample size. We extend these convergence assessment methods for single and multiple chains. Furthermore, we test the performance of the convergence assessment methods on an empirical dataset and conclude that tests for convergence to the same stationary distribution from independent runs are most adequate. Additionally,we developed an automatic procedure that finds the optimal burnin in the cases we studied. All methods we tested are implemented in the open source software RevBayes (http://www.revbayes.net/).
|
|
| 6. |
- Karami, Moein, et al.
(author)
-
Designing efficient randstrobes for sequence similarity analyses
- 2024
-
In: Bioinformatics. - 1367-4803 .- 1367-4811. ; 40:4
-
Journal article (peer-reviewed)abstract
- Motivation: Substrings of length k, commonly referred to as k-mers, play a vital role in sequence analysis. However, k-mers are limited to exact matches between sequences leading to alternative constructs. We recently introduced a class of new constructs, strobemers, that can match across substitutions and smaller insertions and deletions. Randstrobes, the most sensitive strobemer proposed in Sahlin (Effective sequence similarity detection with strobemers. Genome Res 2021a;31:2080–94. https://doi.org/10.1101/gr.275648.121), has been used in several bioinformatics applications such as read classification, short-read mapping, and read overlap detection. Recently, we showed that the more pseudo-random the behavior of the construction (measured in entropy), the more efficient the seeds for sequence similarity analysis. The level of pseudo-randomness depends on the construction operators, but no study has investigated the efficacy.Results: In this study, we introduce novel construction methods, including a Binary Search Tree-based approach that improves time complexity over previous methods. To our knowledge, we are also the first to address biases in construction and design three metrics for measuring bias. Our evaluation shows that our methods have favorable speed and sampling uniformity compared to existing approaches. Lastly, guided by our results, we change the seed construction in strobealign, a short-read mapper, and find that the results change substantially. We suggest combining the two results to improve strobealign’s accuracy for the shortest reads in our evaluated datasets. Our evaluation highlights sampling biases that can occur and provides guidance on which operators to use when implementing randstrobes.Availability and implementation: All methods and evaluation benchmarks are available in a public Github repository at https://github.com/Moein-Karami/RandStrobes. The scripts for running the strobealign analysis are found at https://github.com/NBISweden/strobealign-evaluation.
|
|
| 7. |
- Maier, Benjamin Dominik, 1997-, et al.
(author)
-
Entropy predicts sensitivity of pseudorandom seeds
- 2023
-
In: Genome Research. - 1088-9051 .- 1549-5469. ; 33:7, s. 1162-1174
-
Journal article (peer-reviewed)abstract
- Seed design is important for sequence similarity search applications such as read mapping and average nucleotide identity (ANI) estimation. Although k-mers and spaced k-mers are likely the most well-known and used seeds, sensitivity suffers at high error rates, particularly when indels are present. Recently, we developed a pseudorandom seeding construct, strobemers, which was empirically shown to have high sensitivity also at high indel rates. However, the study lacked a deeper understanding of why. In this study, we propose a model to estimate the entropy of a seed and find that seeds with high entropy, according to our model, in most cases have high match sensitivity. Our discovered seed randomness–sensitivity relationship explains why some seeds perform better than others, and the relationship provides a framework for designing even more sensitive seeds. We also present three new strobemer seed constructs: mixedstrobes, altstrobes, and multistrobes. We use both simulated and biological data to show that our new seed constructs improve sequence-matching sensitivity to other strobemers. We show that the three new seed constructs are useful for read mapping and ANI estimation. For read mapping, we implement strobemers into minimap2 and observe 30% faster alignment time and 0.2% higher accuracy than using k-mers when mapping reads at high error rates. As for ANI estimation, we find that higher entropy seeds have a higher rank correlation between estimated and true ANI.
|
|
| 8. |
|
|
| 9. |
- Namias, Alice, et al.
(author)
-
Nanopore sequencing of PCR products enables multicopy gene family reconstruction
- 2023
-
In: Computational and Structural Biotechnology Journal. - 2001-0370. ; 21, s. 3656-3664
-
Journal article (peer-reviewed)abstract
- The importance of gene amplifications in evolution is more and more recognized. Yet, tools to study multi-copy gene families are still scarce, and many such families are overlooked using common sequencing methods. Haplotype reconstruction is even harder for polymorphic multi-copy gene families. Here, we show that all variants (or haplotypes) of a multi-copy gene family present in a single genome, can be obtained using Oxford Nanopore Technologies sequencing of PCR products, followed by steps of mapping, SNP calling and haplotyping. As a proof of concept, we acquired the sequences of highly similar variants of the cidA and cidB genes present in the genome of the Wolbachia wPip, a bacterium infecting Culex pipiens mosquitoes. Our method relies on a wide database of cid genes, previously acquired by cloning and Sanger sequencing. We addressed problems commonly faced when using mapping approaches for multi-copy gene families with highly similar variants. In addition, we confirmed that PCR amplification causes frequent chimeras which have to be carefully considered when working on families of recombinant genes. We tested the robustness of the method using a combination of bioinformatics (read simulations) and molecular biology approaches (sequence acquisitions through cloning and Sanger sequencing, specific PCRs and digital droplet PCR). When different haplotypes present within a single genome cannot be reconstructed from short reads sequencing, this pipeline confers a high throughput acquisition, gives reliable results as well as insights of the relative copy numbers of the different variants.
|
|
| 10. |
- Nystedt, Björn, et al.
(author)
-
The Norway spruce genome sequence and conifer genome evolution
- 2013
-
In: Nature. - : Nature Publishing Group. - 0028-0836 .- 1476-4687. ; 497:7451, s. 579-584
-
Journal article (peer-reviewed)abstract
- Conifers have dominated forests for more than 200 million years and are of huge ecological and economic importance. Here we present the draft assembly of the 20-gigabase genome of Norway spruce (Picea abies), the first available for any gymnosperm. The number of well-supported genes (28,354) is similar to the >100 times smaller genome of Arabidopsis thaliana, and there is no evidence of a recent whole-genome duplication in the gymnosperm lineage. Instead, the large genome size seems to result from the slow and steady accumulation of a diverse set of long-terminal repeat transposable elements, possibly owing to the lack of an efficient elimination mechanism. Comparative sequencing of Pinus sylvestris, Abies sibirica, Juniperus communis, Taxus baccata and Gnetum gnemon reveals that the transposable element diversity is shared among extant conifers. Expression of 24-nucleotide small RNAs, previously implicated in transposable element silencing, is tissue-specific and much lower than in other plants. We further identify numerous long (>10,000 base pairs) introns, gene-like fragments, uncharacterized long non-coding RNAs and short RNAs. This opens up new genomic avenues for conifer forestry and breeding.
|
|
