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

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. On the other hand, finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations of distinct integers, some distance metrics have been extensively studied. We investigate the median and closest problems on permutations over the following metrics: breakpoint distance, swap distance, block-interchange distance, short-block-move distance, and transposition distance. In biological applications some values are usually very small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation regarding some metrics of distance, even for only $$k = 3$$ permutations; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics when parameterized by the target distance d.

Luís Cunha

Ignasi Sau

Uéverton Souza

On the parameterized complexity of the median and closest problems under some permutation metrics

关于某些置换度量下中位数和最近问题的参数化复杂性

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 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 .

Abbreviation	Algorithms Mol Biol
Journal Impact	1.35
Quartiles(Global)	MATHEMATICAL & COMPUTATIONAL BIOLOGY(Q3)

ISSN	1748-7188
h-index	40

Publication Information	Publisher: BioMed Central Ltd，Publishing cycle: Irregular，Journal Type: journal，Open Access Journals: Yes
Basic data	Year of publication: 2006，Proportion of original research papers: 100.00%，Self Citation Rate:6.70%， Gold OA Rate: 100.00%
Journal Fees	$2390Details
Average review cycle	网友分享经验：>12周，或约稿
Average recruitment ratio	网友分享经验：较易

Algorithms for Molecular Biology

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience

On the parameterized complexity of the median and closest problems under some permutation metrics

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

On the parameterized complexity of the median and closest problems under some permutation metrics

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