Algorithms for Molecular Biology
Издатель: Springer Nature · ISSN 1748-7188,1748-7188 · 25 статей
-
Mutational signature refitting on sparse pan-cancer data
Background Mutational processes shape cancer genomes, leaving characteristic marks that are termed signatures. The level of activity of each such process, or its signature exposure, provides important information on the disease,...
-
Estimation of substitution and indel rates via k-mer statistics
Methods utilizing $$k$$ k -mers are widely used in bioinformatics, yet our understanding of their statistical properties under realistic mutation models remains incomplete. Previously, substitution-only mutation models have been...
-
A k-mer-based estimator of the substitution rate between repetitive sequences
Background K-mer-based analysis of genomic data is ubiquitous, but the presence of repetitive k-mers continues to pose problems for the accuracy of many methods. For example, the Mash tool (Ondov et al 2016) can accurately estimate the...
-
Haplotype-aware long-read error correction
Error correction of long reads is an important initial step in genome assembly workflows. For organisms with ploidy greater than one, it is important to preserve haplotype-specific variation during read correction. This challenge has...
-
Extension of partial atom-to-atom maps: uniqueness and algorithms
Chemical reaction databases typically report the molecular structures of reactant and product compounds, as well as their stoichiometry, but lack information, in particular, on the correspondence of reactant and product atoms. These...
-
Lossless pangenome indexing using tag arrays
Pangenome graphs represent the genomic variation by encoding multiple haplotypes within a unified graph structure. However, efficient and lossless indexing of such structures remains challenging due to the scale and complexity of...
-
Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer
Background Several recent cancer phylogeny inference methods have used the k -Dollo evolutionary model for single-nucleotide variants, which requires a phylogeny T on binary sequencing data matrix B such that each variant is gained once...
-
Probing transcription factor subsets in gene regulatory networks
Transcription factors (TFs) are essential players in the regulation of gene expression and thus have been the subject of interest in the context of diseases and the manipulation of specific cell functions or pathways. The complex...
-
Comparing the ability of embedding methods on metabolic hypergraphs for capturing taxonomy-based features
Background Metabolic networks are complex systems that describe the biochemical reactions within an organism through pairwise interactions between chemical compounds. While this representation is widely used to study biological...
-
Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs
Elastic Degenerate ( ED ) strings and Elastic Founder ( EF ) graphs, here collectively named variable strings, are two representations of acyclic components of pangenomes which extend the well-known notion of indeterminate string....
-
An efficient algorithm for exploring RNA branching conformations under the nearest-neighbor thermodynamic model
Background In the Nearest-Neighbor Thermodynamic Model, a standard approach for RNA secondary structure prediction, the energy of the multiloops is modeled using a linear entropic penalty governed by three branching parameters. Although...
-
Inferring and summarizing tumor phylogenies from bulk DNA data
Background Cancer phylogenies are key to understanding tumor evolution. However, due to the uncertainty in phylogenetic estimation, one typically infers many, equally-plausible phylogenies from bulk DNA sequencing data of tumors,...
-
Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation
The $$\mathcal {C}$$ C - Orientation problem asks whether it is possible to orient an undirected graph to a directed phylogenetic network of a desired network class $$\mathcal {C}$$ C . This problem arises, for example, when visualising...
-
Computing double-pushout graph transformation rules and atom-to-atom maps from KEGG RCLASS data
Background Atom-to-atom maps play an important role in many applications. However, they are often difficult to obtain. The KEGG reaction database does not provide atom-to-atom maps for its reactions and instead offers a description of...
-
Improving spliced alignment by modeling splice sites with deep learning
Motivation Spliced alignment refers to the alignment of messenger RNA (mRNA) or protein sequences to eukaryotic genomes. It plays a critical role in gene annotation and the study of gene functions. Accurate spliced alignment demands...
-
Engineering rank queries on bit vectors and strings
Adding rank support to strings over a fixed-sized alphabet has numerous applications. Prominent among those is the (bidirectional) FM-Index which is commonly utilized to index and analyze genomic data. At its core lies the rank...
-
RNA triplet repeats: improved algorithms for structure prediction and interactions
RNAs composed of Triplet Repeats (TR) have recently attracted much attention in the field of synthetic biology. We study the mimimum free energy (MFE) secondary structures of such RNAs and give improved algorithms to compute the MFE and...
-
RNA inverse folding can be solved in linear time for structures without isolated stacks or base pairs
Inverse folding is a classic instance of negative RNA design which consists in finding a sequence that uniquely folds into a target secondary structure with respect to energy minimization. A breakthrough result of Bonnet et al. shows...
-
Orthology and near-cographs in the context of phylogenetic networks
Orthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of orthology estimates without prior knowledge of the...
-
Finding maximum common contractions between phylogenetic networks
In this paper, we lay the groundwork on the comparison of phylogenetic networks based on edge contractions and expansions as edit operations, as originally proposed by Robinson and Foulds to compare trees. We prove that these operations...
-
Exclusive functional signatures for gene annotation with vast OpenOrd layout
A biological study can produce a limited number of marker genes, not large enough to be used in gene set enrichment analysis. Here we suggest VOL-Gene, a graph-based algorithm that partitions all genes into non-overlapping classes of...
-
The path-label reconciliation (PLR) dissimilarity measure for gene trees
Background In this study, we investigate the problem of comparing gene trees reconciled with the same species tree using a novel semi-metric, called the Path-Label Reconciliation (PLR) dissimilarity measure. This approach not only...
-
b-move: faster lossless approximate pattern matching in a run-length compressed index
Background Due to the increasing availability of high-quality genome sequences, pan-genomes are gradually replacing single consensus reference genomes in many bioinformatics pipelines to better capture genetic diversity. Traditional...
-
NANUQ^+: A divide-and-conquer approach to network estimation
Inference of a species network from genomic data remains a difficult problem, with recent progress mostly limited to the level-1 case. However, inference of the Tree of Blobs of a network, showing only the network’s cut edges, can be...
-
Swiftly identifying strongly unique k-mers
Motivation Short DNA sequences of length k that appear in a single location (e.g., at a single genomic position, in a single species from a larger set of species, etc.) are called unique k-mers . They are useful for placing sequenced...