ALGORITHMS FOR MOLECULAR BIOLOGY 发表关于生物序列和结构分析、系统发育重建、组合算法和机器学习的新算法的文章。感兴趣的领域包括但不限于：RNA 和蛋白质结构分析算法、基因预测和基因组分析、比较序列分析和比对、系统发育、基因表达、机器学习和组合算法。在适当的情况下，手稿应描述对现实世界数据的应用。但是，如果预期未来将应用于生物数据，或者如果它们解决了分子生物学中新计算问题的复杂性或近似问题，那么纯算法论文也受到欢迎。如果有关新颖软件工具的文章包含一些算法上有趣的方面，则将被考虑发表。

The journal "Algorithms for Molecular Biology" publishes research articles on new algorithms related to biological sequence and structure analysis, phylogenetic reconstruction, combinatorial algorithms, and machine learning. Areas of interest include, but are not limited to: algorithms for RNA and protein structure analysis, gene prediction and genomic analysis, comparative sequence analysis and alignment, phylogenetics, gene expression, machine learning, and combinatorial algorithms. Manuscripts should describe applications to real-world data when appropriate. However, pure algorithm papers will also be welcomed if they are expected to be applied to biological data in the future or if they address the complexity or approximation issues of new computational problems in molecular biology. Articles that discuss novel software tools and include interesting algorithmic aspects will also be considered for publication.

《Algorithms for Molecular Biology》期刊发表关于生物序列和结构分析、系统发育重建、组合算法和机器学习的新算法的研究文章。感兴趣的领域包括但不限于：RNA和蛋白质结构分析算法、基因预测和基因组分析、比较序列分析和比对、系统发育、基因表达、机器学习和组合算法。在适当的情况下，手稿应描述对现实世界数据的应用。然而，如果预期未来将应用于生物数据，或者如果它们解决了分子生物学中新计算问题的复杂性或近似问题，那么纯算法论文也会受到欢迎。如果有关新颖软件工具的文章包含一些算法上有趣的方面，也将被考虑发表。

Algorithms for Molecular Biology

The tree of blobs of a species network shows only the tree-like aspects of relationships of taxa on a network, omitting information on network substructures where hybridization or other types of lateral transfer of genetic information occur. By isolating such regions of a network, inference of the tree of blobs can serve as a starting point for a more detailed investigation, or indicate the limit of what may be inferrable without additional assumptions. Building on our theoretical work on the identifiability of the tree of blobs from gene quartet distributions under the Network Multispecies Coalescent model, we develop an algorithm, TINNiK, for statistically consistent tree of blobs inference. We provide examples of its application to both simulated and empirical datasets, utilizing an implementation in the MSCquartets 2.0 R package.

Elizabeth S. Allman

Hector Baños

Jonathan D. Mitchell

John A. Rhodes

TINNiK: inference of the tree of blobs of a species network under the coalescent model

TINNiK：在溯祖模型下推断物种网络的树状斑点

Abstract Background Commonly, sequence and structure elements are assumed to evolve congruently, such that homologous sequence positions correspond to homologous structural features. Assuming congruent evolution, alignments based on sequence and structure similarity can therefore optimize both similarities at the same time in a single alignment. To model incongruent evolution, where sequence and structural features diverge positionally, we recently introduced bi-alignments . This generalization of sequence and structure-based alignments is best understood as alignments of two distinct pairwise alignments of the same entities: one modeling sequence similarity, the other structural similarity. Results Optimal bi-alignments with affine gap costs (or affine shift cost) for two constituent alignments can be computed exactly in quartic space and time. Even bi-alignments with affine shift and gap cost, as well as bi-alignment with sub-additive gap cost are optimized efficiently. Affine gap-cost bi-alignment of large proteins ( $$\sim 930$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∼</mml:mo> <mml:mn>930</mml:mn> </mml:mrow> </mml:math> aa) can be computed. Conclusion Affine cost bi-alignments are of practical interest to study shifts of protein sequences and protein structures relative to each other. Availability The affine cost bi-alignment algorithm has been implemented in Python 3 and Cython. It is available as free software from https://github.com/s-will/BiAlign/releases/tag/v0.3 and as bioconda package .

Peter F. Stadler

Sebastian Will

Bi-alignments with affine gaps costs

具有仿射间隙成本的双重比对

Phylogenetic networks are mathematical models of evolutionary processes involving reticulate events such as hybridization, recombination, or horizontal gene transfer. One of the crucial notions in phylogenetic network modelling is displayed tree, which is obtained from a network by removing a set of reticulation edges. Displayed trees may represent an evolutionary history of a gene family if the evolution is shaped by reticulation events.We address the problem of inferring an optimal tree displayed by a network, given a gene tree G and a tree-child network N, under the deep coalescence and duplication costs. We propose an O(mn)-time dynamic programming algorithm (DP) to compute a lower bound of the optimal displayed tree cost, where m and n are the sizes of G and N, respectively. In addition, our algorithm can verify whether the solution is exact. Moreover, it provides a set of reticulation edges corresponding to the obtained cost. If the cost is exact, the set induces an optimal displayed tree. Otherwise, the set contains pairs of conflicting edges, i.e., edges sharing a reticulation node. Next, we show a conflict resolution algorithm that requires [Formula: see text] invocations of DP in the worst case, where r is the number of reticulations. We propose a similar [Formula: see text]-time algorithm for level-k tree-child networks and a branch and bound solution to compute lower and upper bounds of optimal costs. We also extend the algorithms to a broader class of phylogenetic networks. Based on simulated data, the average runtime is [Formula: see text] under the deep-coalescence cost and [Formula: see text] under the duplication cost.Despite exponential complexity in the worst case, our algorithms perform significantly well on empirical and simulated datasets, due to the strategy of resolving internal dissimilarities between gene trees and networks. Therefore, the algorithms are efficient alternatives to enumeration strategies commonly proposed in the literature and enable analyses of complex networks with dozens of reticulations.

Marcin Wawerka

Dawid Dąbkowski

Natalia Rutecka

Agnieszka Mykowiecka

Paweł Górecki

Embedding gene trees into phylogenetic networks by conflict resolution algorithms

通过冲突解决算法将基因树嵌入系统发育网络

Cell signaling pathways, which are a series of reactions that start at receptors and end at transcription factors, are basic to systems biology. Properly modeling the reactions in such pathways requires directed hypergraphs, where an edge is now directed between two sets of vertices. Inferring a pathway by the most parsimonious series of reactions corresponds to finding a shortest hyperpath in a directed hypergraph, which is NP-complete. The current state-of-the-art for shortest hyperpaths in cell signaling hypergraphs solves a mixed-integer linear program to find an optimal hyperpath that is restricted to be acyclic, and offers no efficiency guarantees.We present, for the first time, a heuristic for general shortest hyperpaths that properly handles cycles, and is guaranteed to be efficient. We show the heuristic finds provably optimal hyperpaths for the class of singleton-tail hypergraphs, and also give a practical algorithm for tractably generating all source-sink hyperpaths. The accuracy of the heuristic is demonstrated through comprehensive experiments on all source-sink instances from the standard NCI-PID and Reactome pathway databases, which show it finds a hyperpath that matches the state-of-the-art mixed-integer linear program on over 99% of all instances that are acyclic. On instances where only cyclic hyperpaths exist, the heuristic surpasses the state-of-the-art, which finds no solution; on every such cyclic instance, enumerating all source-sink hyperpaths shows the solution found by the heuristic was in fact optimal.The new shortest hyperpath heuristic is both fast and accurate. This makes finding source-sink hyperpaths, which in general may contain cycles, now practical for real cell signaling networks.Source code for the hyperpath heuristic in a new tool we call Hhugin (as well as for hyperpath enumeration, and all dataset instances) is available free for non-commercial use at http://hhugin.cs.arizona.edu.

Spencer Krieger

John Kececioglu

Heuristic shortest hyperpaths in cell signaling hypergraphs

细胞信号超图中启发式最短超路径

The early development of a zygote can be mathematically described by a developmental tree. To compare developmental trees of different species, we need to define distances on trees. If children cells after a division are not distinguishable, developmental trees are represented by the space $\mathcal{T}$ of rooted trees with possibly repeated labels, where all vertices are unordered. If children cells after a division are partially distinguishable, developmental trees are represented by the space $\mathcal{P}$ of rooted trees with possibly repeated labels, where vertices can be ordered or unordered. On $\mathcal{T}$, the space of rooted unordered trees with possibly repeated labels, we define two metrics: the best-match metric and the left-regular metric, which show some advantages over existing methods. On $\mathcal{P}$, the space of rooted labeled trees with ordered or unordered vertices, there is no metric, and we define a semimetric, which is a variant of the best-match metric. To compute the best-match distance between two trees, the expected time complexity and worst-case time complexity are both $\mathcal{O}(n^2)$, where $n$ is the tree size. To compute the left-regular distance between two trees, the expected time complexity is $\mathcal{O}(n)$, and the worst-case time complexity is $\mathcal{O}(n\log n)$. For rooted labeled trees with (fully/partially) unordered vertices, we define metrics (semimetric) that have fast algorithms to compute and have advantages over existing methods. Such trees also appear outside of developmental biology, and such metrics can be applied to other types of trees which have more extensive applications, especially in molecular biology.

Yue Wang

Two metrics on rooted unordered trees with labels

带标签的根无序树的两个度量

The B cell lineage tree encapsulates the successive phases of B cell differentiation and maturation, transitioning from hematopoietic stem cells to mature, antibody-secreting cells within the immune system. Mathematically, this lineage can be conceptualized as an evolutionary tree, where each node represents a distinct stage in B cell development, and the edges reflect the differentiation pathways. To compare these lineage trees, a rigorous mathematical metric is essential. Analyzing B cell lineage trees mathematically and quantifying changes in lineage attributes over time necessitates a comparison methodology capable of accurately assessing and measuring these changes. Addressing the intricacies of multiple B cell lineage tree comparisons, this study introduces a novel metric that enhances the precision of comparative analysis. This metric is formulated on principles of metric theory and evolutionary biology, quantifying the dissimilarities between lineage trees by measuring branch length distance and weight. By providing a framework for systematically classifying lineage trees, this metric facilitates the development of predictive models that are crucial for the creation of targeted immunotherapy and vaccines. To validate the effectiveness of this new metric, synthetic datasets that mimic the complexity and variability of real B cell lineage structures are employed. We demonstrated the ability of the new metric method to accurately capture the evolutionary nuances of B cell lineages.

Mahsa Farnia

Nadia Tahiri

New generalized metric based on branch length distance to compare B cell lineage trees

基于分支长度距离的新广义度量用于比较B细胞谱系树

Abstract Metric multidimensional scaling is one of the classical methods for embedding data into low-dimensional Euclidean space. It creates the low-dimensional embedding by approximately preserving the pairwise distances between the input points. However, current state-of-the-art approaches only scale to a few thousand data points. For larger data sets such as those occurring in single-cell RNA sequencing experiments, the running time becomes prohibitively large and thus alternative methods such as PCA are widely used instead. Here, we propose a simple neural network-based approach for solving the metric multidimensional scaling problem that is orders of magnitude faster than previous state-of-the-art approaches, and hence scales to data sets with up to a few million cells. At the same time, it provides a non-linear mapping between high- and low-dimensional space that can place previously unseen cells in the same embedding.

Stefan Canzar

Van Hoan Do

Slobodan Jelić

Sören Laue

Domagoj Matijević

Tomislav Prusina

Metric multidimensional scaling for large single-cell datasets using neural networks

使用神经网络的大规模单细胞数据集的度量多维缩放

A colored de Bruijn graph (also called a set of k-mer sets), is a set of k-mers with every k-mer assigned a set of colors. Colored de Bruijn graphs are used in a variety of applications, including variant calling, genome assembly, and database search. However, their size has posed a scalability challenge to algorithm developers and users. There have been numerous indexing data structures proposed that allow to store the graph compactly while supporting fast query operations. However, disk compression algorithms, which do not need to support queries on the compressed data and can thus be more space-efficient, have received little attention. The dearth of specialized compression tools has been a detriment to tool developers, tool users, and reproducibility efforts. In this paper, we develop a new tool that compresses colored de Bruijn graphs to disk, building on previous ideas for compression of k-mer sets and indexing colored de Bruijn graphs. We test our tool, called ESS-color, on various datasets, including both sequencing data and whole genomes. ESS-color achieves better compression than all evaluated tools and all datasets, with no other tool able to consistently achieve less than 44% space overhead. The software is available at http://github.com/medvedevgroup/ESSColor .

Amatur Rahman

Yoann Dufresne

Paul Medvedev

Compression algorithm for colored de Bruijn graphs

彩色de Bruijn图的压缩算法

Abstract Background Given a sequencing read, the broad goal of read mapping is to find the location(s) in the reference genome that have a “similar sequence”. Traditionally, “similar sequence” was defined as having a high alignment score and read mappers were viewed as heuristic solutions to this well-defined problem. For sketch-based mappers, however, there has not been a problem formulation to capture what problem an exact sketch-based mapping algorithm should solve. Moreover, there is no sketch-based method that can find all possible mapping positions for a read above a certain score threshold. Results In this paper, we formulate the problem of read mapping at the level of sequence sketches. We give an exact dynamic programming algorithm that finds all hits above a given similarity threshold. It runs in $$\mathcal {O} (|t| + |p| + \ell ^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>|</mml:mo> <mml:mi>t</mml:mi> <mml:mo>|</mml:mo> <mml:mo>+</mml:mo> <mml:mo>|</mml:mo> <mml:mi>p</mml:mi> <mml:mo>|</mml:mo> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time and $$\mathcal {O} (\ell \log \ell )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>log</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> space, where | t | is the number of $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -mers inside the sketch of the reference, | p | is the number of $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -mers inside the read’s sketch and $$\ell$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> is the number of times that $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -mers from the pattern sketch occur in the sketch of the text. We evaluate our algorithm’s performance in mapping long reads to the T2T assembly of human chromosome Y, where ampliconic regions make it desirable to find all good mapping positions. For an equivalent level of precision as minimap2, the recall of our algorithm is 0.88, compared to only 0.76 of minimap2.

acBWQ6	Algorithms Mol Biol
Journal Impact	1.35
mbqgSu	MATHEMATICAL & COMPUTATIONAL BIOLOGY(Q3)
xGGr6y	SCI Q4中科院 4 区

ISSN	1748-7188
h-index	40
hQoIdU	生物学(4区)生物学生化研究方法(4区)生物学生物工程与应用微生物(4区)生物学数学与计算生物学(4区)

u9zg3I	计算机科学数学生物化学遗传学生物化学基因算法人工智能程序设计语言组合数学数据挖掘哲学统计操作系统计算生物学理论计算机科学数学分析物理离散数学机器学习工程类认识论集合（抽象数据类型）数学优化
+5d/bs	e+/GRg: BioMed Central Ltd，uzYam8: Irregular，dxwaWB: journal，8x2mMQ: Xn96QY
ak9yM6	A7IHrH: 2006，sQJ/D8: 100.00%，sE9og+:6.70%， wzlKC/: 100.00%
OtlFwL	$23908By/Hf
JrpmBe	网友分享经验：>12周，或约稿
jdemjX	网友分享经验：较易

Algorithms for Molecular Biology

uM3Gfz

sZFHBm

sZFHBm

sZFHBm

sZFHBm

Hi2Sc4

e7MLUV

XjnQ+b

Kq5Kd6

LB2xFn

XmiM++

TINNiK: inference of the tree of blobs of a species network under the coalescent model

Bi-alignments with affine gaps costs

Embedding gene trees into phylogenetic networks by conflict resolution algorithms

Heuristic shortest hyperpaths in cell signaling hypergraphs

Two metrics on rooted unordered trees with labels

TINNiK: inference of the tree of blobs of a species network under the coalescent model

New generalized metric based on branch length distance to compare B cell lineage trees

Metric multidimensional scaling for large single-cell datasets using neural networks

Compression algorithm for colored de Bruijn graphs

ESKEMAP: exact sketch-based read mapping