检索结果-内蒙古大学图书馆

The Evolution and Implications of the Inosine tRNA Modification

Journal of Molecular Biology 2025年 169187页

作者： van der Gulik, Peter T.S. Hoff, Wouter D. Algorithms and Complexity Group Centrum Wiskunde & Informatica P.O. Box 94079 Amsterdam 1090 GB Netherlands Department of Microbiology and Molecular Genetics Oklahoma State University Stillwater 74078 OK United States

Ever since the legendary publication by Francis Crick in JMB introducing the wobble hypothesis in 1966, inosine has been a permanent part of molecular biology. This review aims to integrate the rich array of novel insights emerging from subsequent research on the adenine-to-inosine modification of tRNA, with an emphasis on the results obtained during the last 5 years. Both the grand panorama of 4 billion years of evolution of life and the medical implications of defects in inosine modification will be reviewed. The most salient insights are that: (1) inosine at position 34 (the first position in the anticodon) is not universally present in the tree of life;(2) in many bacteria just a single homodimeric enzyme (TadA) is responsible for both tRNA inosine modification and mRNA inosine modification;(3) rapid progress is currently being made both in the molecular understanding of the heterodimeric ADAT2/ADAT3 enzyme responsible for inosine modifications in eukaryotes and in experimental capabilities for monitoring both the cytoplasmic tRNA pool and their modifications;(4) for selected tRNAs, inosine modification at position 37 has been demonstrated but this modification remains under-studied;(5) modification of tRNAs known to contain inosine can be incomplete;(6) the GC content of the T-stem is of great importance for wobble behavior, including wobbling behavior of inosine;and (7) the tRNA inosine modification is of direct relevance to human disease. In summary, research on inosine continues to yield important novel insights. © 2025 The Authors

关键词： Eukaryogenesis Inosine Modopathies Nanopore Wobble

来源：评论

学校读者我要写书评

暂无评论

A Tight Subexponential-Time Algorithm for Two-Page Book Embedding 51

A Tight Subexponential-Time Algorithm for Two-Page Book Embe...

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Ganian, Robert Müller, Haiko Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz Algorithms and Complexity Group TU Wien Austria School of Computing University of Leeds United Kingdom

ISBN: (纸本)9783959773225

A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into "pages", which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are of special importance as they are both NP-hard to compute and have specific applications. We obtain a 2O(√n) algorithm for computing a book embedding of an n-vertex graph on two pages – a result which is asymptotically tight under the Exponential Time Hypothesis. As a key tool in our approach, we obtain a single-exponential fixed-parameter algorithm for the same problem when parameterized by the treewidth of the input graph. We conclude by establishing the fixed-parameter tractability of computing minimum-page book embeddings when parameterized by the feedback edge number, settling an open question arising from previous work on the problem. © Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani, and Mateusz Rychlicki.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Lossy Kernelization of Same-Size Clustering 1

引用

17th International Computer Science Symposium in Russia, CSR 2022

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Purohit, Nidhi Siminov, Kirill Department of Informatics University of Bergen Bergen Norway Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (数字)9783031095740

ISBN: (纸本)9783031095733

In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters, from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem, parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existences of an (exact) kernel of polynomial size and a PTAS. © 2022, Springer Nature Switzerland AG.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Path-contractions, edge deletions and connectivity preservation 25

Path-contractions, edge deletions and connectivity preservat...

引用

25th European Symposium on algorithms, ESA 2017

作者： Gutin, Gregory Ramanujan, M.S. Reidl, Felix Wahlström, Magnus Algorithms and Complexity Group TU Wien Vienna Austria Royal Holloway University Egham United Kingdom

ISBN: (纸本)9783959770491

We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, Vertexdeletion Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while deleting exactly k vertices, and Path-contraction Preserving Strong Connectivity, in which the operation of path contraction on arcs is used instead. The parameterized tractability of this last problem was posed in [Bang-Jensen and Yeo, Discrete Applied Math 2008] as an open question and we answer it here in the negative: both variants of preserving strong connectivity are W[1]-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable (FPT) and we provide an FPT algorithm that solves Weighted Biconnectivity Deletion. Further, we show that the unweighted case even admits a randomized polynomial kernel. All our results provide further interesting data points for the systematic study of connectivitypreservation constraints in the parameterized setting.

关键词： Undirected graphs

来源：评论

学校读者我要写书评

暂无评论

Parameterised Partially-Predrawn Crossing Number 38

Parameterised Partially-Predrawn Crossing Number

引用

38th International Symposium on Computational Geometry, SoCG 2022

作者： Hamm, Thekla Hlinený, Petr Algorithms and Complexity Group TU Wien Austria Faculty of Informatics Masaryk University Brno Czech Republic

ISBN: (纸本)9783959772273

Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predrawn crossing number to be the smallest number of crossings in any drawing of a graph, part of which is prescribed on the input (not counting the prescribed crossings). Our main result - an FPT-algorithm to compute the partially predrawn crossing number - combines advanced ideas from research on the classical crossing number and so called partial planarity in a very natural but intricate way. Not only do our techniques generalise the known FPT-algorithm by Grohe for computing the standard crossing number, they also allow us to substantially improve a number of recent parameterised results for various drawing extension problems. © Thekla Hamm and Petr Hlinn;licensed under Creative Commons License CC-BY 4.0

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Boundary Labeling in a Circular Orbit 32

Boundary Labeling in a Circular Orbit

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Bonerath, Annika Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Wulms, Jules University of Bonn Germany Algorithms and Complexity Group TU Wien Austria TU Eindhoven Netherlands Chair for Efficient Algorithms TU Munich Germany

ISBN: (纸本)9783959773430

Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights. © Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting 16

Discovering Archipelagos of Tractability for Constraint Sati...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Robert Ganian M. S. Ramanujan Stefan Szeider Algorithms and Complexity Group

ISBN: (纸本)9781510819672

The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A central line of research is concerned with the identification of classes of instances for which CSP can be solved in polynomial time; such classes are often called "islands of tractability." A prominent way of defining islands of tractability for CSP is to restrict the relations that may occur in the constraints to a fixed set, called a constraint language, whereas a constraint language is conservative if it contains all unary relations. Schaefer's famous Dichotomy Theorem (STOC 1978) identifies all islands of tractability in terms of tractable constraint languages over a Boolean domain of values. Since then many extensions and generalizations of this result have been obtained. Recently, Bulatov (TOCL 2011, JACM 2013) gave a full characterization of all islands of tractability for CSP and the counting version #CSP that are defined in terms of conservative constraint languages. This paper addresses the general limit of the mentioned tractability results for CSP and #CSP, that they only apply to instances where all constraints belong to a single tractable language (in general, the union of two tractable languages isn't tractable). We show that we can overcome this limitation as long as we keep some control of how constraints over the various considered tractable languages interact with each other. For this purpose we utilize the notion of a strong backdoor of a CSP instance, as introduced by Williams et al. (IJCAI 2003), which is a set of variables that when instantiated moves the instance to an island of tractability, i.e., to a tractable class of instances. We consider strong backdoors into scattered classes, consisting of CSP instances where each connected component belongs entirely to some class from a list of tractable classes. Figuratively speaking, a scattered class constitutes an archipela

关键词： chip scale packaging communicating sequential processes phosphocellulose Language islands constraint satisfaction problems archipelagoes Constraint Polynomial time

来源：评论

学校读者我要写书评

暂无评论

Deterministic Constrained Multilinear Detection 48

Deterministic Constrained Multilinear Detection

引用

48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023

作者： Brand, Cornelius Korchemna, Viktoriia Skotnica, Michael Algorithms and Complexity Group TU Wien Austria Department of Applied Mathematics Charles University Prague Czech Republic

ISBN: (纸本)9783959772921

We extend the algebraic techniques of Brand and Pratt (ICALP’21) for deterministic detection of k-multilinear monomials in a given polynomial with non-negative coefficients to the more general situation of detecting colored k-multilinear monomials that satisfy additional constraints on the multiplicities of the colors appearing in them. Our techniques can be viewed as a characteristic-zero generalization of the algebraic tools developed by Guillemot and Sikora (MFCS’10) and Björklund, Kaski and Kowalik (STACS’13) As applications, we recover the state-of-the-art deterministic algorithms for the Graph Motif problem due to Pinter, Schachnai and Zehavi (MFCS’14), and give new deterministic algorithms for generalizations of certain questions on colored directed spanning trees or bipartite planar matchings running in deterministic time O∗(4k), studied originally by Gutin, Reidl, Wahlström and Zehavi (J. Comp. Sys. Sci. 95,’18). Finally, we give improved randomized algorithms for intersecting three and four matroids of rank k in characteristic zero, improving the record bounds of Brand and Pratt (ICALP’21) from O∗(64k) and O∗(256k), respectively, to O∗(4k). © Cornelius Brand, Viktoriia Korchemna, and Michael Skotnica

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Twin-Width Meets Feedback Edges and Vertex Integrity 19

Twin-Width Meets Feedback Edges and Vertex Integrity

引用

19th International Symposium on Parameterized and Exact Computation, IPEC 2024

作者： Balabán, Jakub Ganian, Robert Rocton, Mathis Faculty of Informatics Masaryk University Brno Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959773539

The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: An asymptotically tight bound between twin-width and the feedback edge number;A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency;An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph. © Jakub Balabán, Robert Ganian, and Mathis Rocton.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A SAT Attack on Rota’s Basis Conjecture 25

A SAT Attack on Rota’s Basis Conjecture

引用

25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022

作者： Kirchweger, Markus Scheucher, Manfred Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Institut für Mathematik Technische Universität Berlin Germany

ISBN: (纸本)9783959772426

The SAT modulo Symmetries (SMS) is a recently introduced framework for dynamic symmetry breaking in SAT instances. It combines a CDCL SAT solver with an external lexicographic minimality checking algorithm. We extend SMS from graphs to matroids and use it to progress on Rota’s Basis Conjecture (1989), which states that one can always decompose a collection of r disjoint bases of a rank r matroid into r disjoint rainbow bases. Through SMS, we establish that the conjecture holds for all matroids of rank 4 and certain special cases of matroids of rank 5. Furthermore, we extend SMS with the facility to produce DRAT proofs. External tools can then be used to verify the validity of additional axioms produced by the lexicographic minimality check. As a byproduct, we have utilized our framework to enumerate matroids modulo isomorphism and to support the investigation of various other problems on matroids. © Markus Kirchweger, Manfred Scheucher, and Stefan Szeider.

关键词： Combinatorial mathematics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：