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

Generalizing the Domain-Gene-Species Reconciliation Framework to Microbial Genes and Domains

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第6期20卷 3511-3522页

作者： Mondal, Abhijit Bansal, Mukul S. Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

Protein domains play an important role in the function and evolution of many gene families. Previous studies have shown that domains are frequently lost or gained during gene family evolution. Yet, most computational approaches for studying gene family evolution do not account for domain-level evolution within genes. To address this limitation, a new three-level reconciliation framework, called the Domain-Gene-Species (DGS) reconciliation model, has been recently developed to simultaneously model the evolution of a domain family inside one or more gene families and the evolution of those gene families inside a species tree. However, the existing model applies only to multi-cellular eukaryotes where horizontal gene transfer is negligible. In this work, we generalize the existing DGS reconciliation model by allowing for the spread of genes and domains across species boundaries through horizontal transfer. We show that the problem of computing optimal generalized DGS reconciliations, though NP-hard, is approximable to within a constant factor, where the specific approximation ratio depends on the "event costs" used. We provide two different approximation algorithms for the problem and demonstrate the impact of the generalized framework using both simulated and real biological data. Our results show that our new algorithms result in highly accurate reconstructions of domain family evolution for microbes.

关键词： Protein domains microbial gene family evolution phylogenetic reconciliation horizontal transfer approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Matching Supply and Demand in Online Parking Reservation Platforms

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2023年第3期24卷 3182-3193页

作者： Karaliopoulos, Merkouris Mastakas, Orestis Chai, Wei Koong Athens Univ Econ & Business Dept Informat Athens 10434 Greece Bournemouth Univ Dept Comp & Informat Bournemouth BH12 5BB England

Our work concerns online parking reservation plat-forms proposed in the last decade to cope with the parking challenge in cities worldwide. Enlisting parking resources from commercial operators (e.g., lots) and individuals (e.g., doorways) and letting drivers make online reservations through mobile apps, those platforms seek to ease transactions between the two sides and best match parking supply with parking demand. This way they maximize their value for drivers and parking space providers but also their revenue out of charged commissions. We distinguish between two types of commissions these platforms typically charge, fixed per transaction and proportional to its value, and formulate the respective optimization problems for the platform revenue maximization. We show that the two problems are NP-hard and design a novel algorithm that can treat both by combining greedy and dynamic programming principles. We study its optimality properties both analytically and experimentally, showing that the algorithm closely tracks optimal solutions for small and moderate problem sizes at run times that are several orders of size smaller than those needed by off-the-shelf ILP solvers. We then analyze real parking data we collected for the period 2018-2020 from the Bournemouth city in UK to realistically model the rich spatiotemporal dynamics of parking demand such as the location, start times and dura-tion of parking events. These datasets drive the experimental evaluation of the proposed algorithm, which reports gains of up to 35% compared to the de facto parking resource reser-vation policy in such platforms. Notably, the highest gains are achieved when the platform operates under constrained supply conditions.

关键词： Optimized production technology approximation algorithms Urban areas Supply and demand Optimization Heuristic algorithms Complexity theory Parking reservation resource sharing optimization sharing economy

来源：评论

学校读者我要写书评

暂无评论

Deletion to scattered graph classes II-improved FPT algorithms for deletion to pairs of graph classes

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期136卷 280-301页

作者： Jacob, Ashwin Majumdar, Diptapriyo Raman, Venkatesh Ben Gurion Univ Negev Beer Sheva Israel Indraprastha Inst Informat Technol Delhi New Delhi India HBNI Inst Math Sci Chennai India

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Pi(1), Pi(2)) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. (c) 2023 Elsevier Inc. All rights reserved.

关键词： Fixed-parameter tractability Scattered graph classes approximation algorithms Interval graphs Chordal graphs Bipartite permutation graphs

来源：评论

学校读者我要写书评

暂无评论

Point-Set Kernel Clustering

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第5期35卷 5147-5158页

作者： Ting, Kai Ming Wells, Jonathan R. Zhu, Ye Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210093 Jiangsu Peoples R China Deakin Univ Sch Informat Technol Geelong Vic 3220 Australia

Measuring similarity between two objects is the core operation in existing clustering algorithms in grouping similar objects into clusters. This paper introduces a new similarity measure called point-set kernel which computes the similarity between an object and a set of objects. The proposed clustering procedure utilizes this new measure to characterize every cluster grown from a seed object. We show that the new clustering procedure is both effective and efficient that enables it to deal with large scale datasets. In contrast, existing clustering algorithms are either efficient or effective. In comparison with the state-of-the-art density-peak clustering and scalable kernel k-means clustering, we show that the proposed algorithm is more effective and runs orders of magnitude faster when applying to datasets of millions of data points, on a commonly used computing machine.

关键词： Kernel Clustering algorithms Density measurement Size measurement Computational efficiency approximation algorithms Shape Cluster analysis kernel clustering point-set kernel data dependent kernel

来源：评论

学校读者我要写书评

暂无评论

Reinforcement Learning With Selective Exploration for Interference Management in mmWave Networks

IEEE TRANSACTIONS ON MACHINE LEARNING IN COMMUNICATIONS AND ...

引用

IEEE TRANSACTIONS ON MACHINE LEARNING IN COMMUNICATIONS AND NETWORKING 2025年 3卷 280-295页

作者： Dinh-van, Son Nguyen, van-Linh Cebecioglu, Berna Bulut Masaracchia, Antonino Higgins, Matthew D. Univ Warwick Sch Engn Warwick Mfg Grp Coventry CV4 7AL England Natl Chung Cheng Univ CCU Adv Inst Mfg High Tech Innovat Chiayi 621301 Taiwan Birmingham City Univ Sch Comp & Digital Technol Birmingham B4 7XG England Queen Mary Univ London Sch Elect Engn & Comp Sci London E1 4NS England

The next generation of wireless systems will leverage the millimeter-wave (mmWave) bands to meet the increasing traffic volume and high data rate requirements of emerging applications (e.g., ultra HD streaming, metaverse, and holographic telepresence). In this paper, we address the joint optimization of beamforming, power control, and interference management in multi-cell mmWave networks. We propose novel reinforcement learning algorithms, including a single-agent-based method (BPC-SA) for centralized settings and a multi-agent-based method (BPC-MA) for distributed settings. To tackle the high-variance rewards caused by narrow antenna beamwidths, we introduce a selective exploration method to guide the agent towards more intelligent exploration. Our proposed algorithms are well-suited for scenarios where beamforming vectors require control in either a discrete domain, such as a codebook, or in a continuous domain. Furthermore, they do not require channel state information, extensive feedback from user equipments, or any searching methods, thus reducing overhead and enhancing scalability. Numerical results demonstrate that selective exploration improves per-user spectral efficiency by up to 22.5% compared to scenarios without it. Additionally, our algorithms significantly outperform existing methods by 50% in terms of per-user spectral effciency and achieve 90% of the per-user spectral efficiency of the exhaustive search approach while requiring only 0.1% of its computational runtime.

关键词： Millimeter wave communication Interference Array signal processing Power control Spectral efficiency Real-time systems Computer architecture Training approximation algorithms Wireless networks Beam training deep reinforcement learning interference management mmWave multi agent power control selective exploration

来源：评论

学校读者我要写书评

暂无评论

Hessian-Aided Random Perturbation (HARP) Using Noisy Zeroth-Order Oracles

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2023年第7期34卷 3717-3726页

作者： Zhu, Jingyi Alibaba Grp Damo Acad Decis Intelligence Lab Resource Optimizat Team Bellevue WA 98004 USA

In stochastic optimization problems where only noisy zeroth-order (ZO) oracles are available, the Kiefer-Wolfowitz algorithm and its randomized counterparts are widely used as gradient estimators. Existing algorithms generate the random perturbations from certain distributions with a zero mean and an isotropic (either identity or scalar) covariance matrix. In contrast, this work considers the generalization where the perturbations may have an anisotropic covariance based on the ZO oracle history. We propose to feed the second-order approximation into the covariance matrix of the random perturbation, so it is dubbed as Hessian-aided random perturbation (HARP). HARP collects two or more (depending on the specific estimator form) ZO oracle calls per iteration to construct the gradient and the Hessian estimators. We prove HARP's almost-surely convergence and derive its convergence rate under standard assumptions. We demonstrate, with theoretical guarantees and numerical experiments, that HARP is less sensitive to ill-conditioning and more query-efficient than other gradient approximation schemes whose random perturbations have an isotropic covariance.

关键词： Perturbation methods Convergence Optimization Covariance matrices Noise measurement approximation algorithms Loss measurement Derivative-free optimization Hessian estimator simultaneous perturbation stochastic approximation (SA)

来源：评论

学校读者我要写书评

暂无评论

Revisiting Multi-Codebook Quantization

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2023年 32卷 2399-2412页

作者： Zhu, Xiaosu Song, Jingkuan Gao, Lianli Gu, Xiaoyan Shen, Heng Tao Univ Elect Sci & Technol China Ctr Future Media Chengdu 611731 Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Univ Elect Sci & Technol China Shenzhen Inst Adv Study Shenzhen 518110 Peoples R China Peng Cheng Lab Shenzhen 518066 Peoples R China Chinese Acad Sci Inst Informat Engn Beijing 100093 Peoples R China

Multi-Codebook Quantization (MCQ) is a generalized version of existing codebook-based quantizations for Approximate Nearest Neighbor (ANN) search. Specifically, MCQ picks one codeword for each sub-codebook independently and takes the sum of picked codewords to approximate the original vector. The objective function involves no constraints, therefore, MCQ theoretically has the potential to achieve the best performance because solutions of other codebook-based quantization methods are all covered by MCQ's solution space under the same codebook size setting. However, finding the optimal solution to MCQ is proved to be NP-hard due to its encoding process, i.e., converting an input vector to a binary code. To tackle this, researchers apply constraints to it to find near-optimal solutions or employ heuristic algorithms that are still time-consuming for encoding. Different from previous approaches, this paper takes the first attempt to find a deep solution to MCQ. The encoding network is designed to be as simple as possible, so the very complex encoding problem becomes simply a feed-forward. Compared with other methods on three datasets, our method shows state-of-the-art performance. Notably, our method is $11\times $ - $38\times $ faster than heuristic algorithms for encoding, which makes it more practical for the real scenery of large-scale retrieval. Our code is publicly available: https://***/DeepMCQ/DeepQ.

关键词： Quantization (signal) Encoding Training Image coding Neural networks Clustering algorithms approximation algorithms Multi-codebook quantization approximate nearest neighbor search retrieval

来源：评论

学校读者我要写书评

暂无评论

The edge-preservation similarity for comparing rooted, unordered, node-labeled trees*

引用

PATTERN RECOGNITION LETTERS 2023年第1期167卷 189-195页

作者： Boria, Nicolas Kiederle, Jana Yger, Florian Blumenthal, David B. PSL Univ Univ Paris Dauphine LAMSADE CNRSUMR7243 Paris France Friedrich Alexander Univ Erlangen Nurnberg Dept Artificial Intelligence Biomed Engn Biomed Network Sci Lab Erlangen Germany Normandie Univ GREYC CNRS ENSICAENUMR 6072 Caen France

Rooted trees are ubiquitous data structures which are used to model hierarchical objects from a plethora of different application domains. For various downstream analysis tasks, measures are needed that quan-tify (dis-)similarity between rooted trees. Many such measures exist, e. g., the widely used tree edit dis-tance (TED). However, there are few algorithms to compute (dis-)similarity measures which are specifi-cally designed for rooted, unordered, node-labeled trees and support input trees of different orders. To close this gap in the literature, we introduce the edge-preservation similarity (EPS). We show how to exactly compute EPS via integer quadratic programming on small instances and present a scalable 4-approximation algorithm. An evaluation on tree representations of pseudoknotted RNA secondary struc-tures and acyclic molecular graphs shows that both exact and approximate (normalized) EPS better preserves functional similarities between the compared RNAs and molecules than the often-used TED. Python implementations of our algorithms and scripts to reproduce the results are available on GitHub: https://***/bionetslab/edge-preservation-similarity . (c) 2023 Elsevier B.V. All rights reserved.

关键词： Tree similarity measures Integer quadratic programming approximation algorithms RNA secondary structures

来源：评论

学校读者我要写书评

暂无评论

Two-Hop Biconnected Components in the Global Liner Shipping Network Reveal International Trade Statuses

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2023年第3期10卷 1564-1574页

作者： Liu, Xueming Xu, Yue Xu, Mengqiao Deng, Wenhui Pan, Linqiang Ng, Adolf K. Y. Huazhong Univ Sci & Technol Sch Artificial Intelligence & Automat Key Lab Image Informat Proc & Intelligent Control Wuhan 430074 Peoples R China Dalian Univ Technol Sch Econ & Management Dalian 116024 Peoples R China BNU HKBU United Int Coll Fac Business & Management Zhuhai 519087 Peoples R China

Over 80% of global trade is carried by sea, and 70% of global seaborne trade by value is realized by liner shipping. The global liner shipping network (GLSN) is essential to facilitating international trade. To explore the transportation mechanism of the GLSN, we study a structure termed "two-hop biconnected component"(TBCC) which is a type of highly robust and efficient connected local structure. We find that TBCC is a salient structural property of the GLSN and is strongly associated with international trade statuses. Ports that appear more frequently in TBCCs tend to gain higher container throughputs in reality and play more important roles in maintaining the overall network robustness. Furthermore, we find that countries belonging to the same TBCCs tend to have closer trading relationships and form meaningful multilateral trade clusters in the future. The discovery of TBCC can help better understand international trade statuses and enable better design of robust and efficient liner shipping service routes.

关键词： Seaports Robustness International trade Heuristic algorithms approximation algorithms Marine vehicles Industries Complex networks network structure network topology transportation systems analysis

来源：评论

学校读者我要写书评

暂无评论

The Discriminative Discrete Basis Problem: Definitions, algorithms, Benchmarking, and Application to Brain's Functional Dynamics

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 1-16页

作者： Haddad, Ali E. E. Najafizadeh, Laleh Univ Basrah Dept Comp Engn Basrah 61004 Iraq Rutgers State Univ Dept Elect & Comp Engn Piscataway NJ 08854 USA

In this paper, considering two Boolean matrices, we tackle the problem of finding a set of Boolean basis vectors that capture the latent components most discriminative of one matrix from another. We refer to this problem as the discriminative discrete basis problem (DDBP). Depending on the symmetry/asymmetry of the problem about the two input matrices, different classes of the DDBP are defined. We present an ensemble of new algorithms, called the discriminative-associative (DASSO) algorithms, to find solutions for these classes of the DDBP. Furthermore, we design a comprehensive, simulation-based benchmarking framework for evaluating the performance of such algorithmic solutions to the DDBP over a wide range of variables, including the effects of disturbances, noise, the geometric features of the latent components within each matrix, and the relationships among these components across the contrasted matrices. As an example application, we demonstrate the utility of the DASSO algorithms in studying the dynamics of the brain function by identifying the cortical activities that discriminate motor from non-motor tasks using recordings obtained via electroencephalography (EEG). The results highlight the location of such discriminating activities in the cortex and the time of their occurrence, which can lead to the design of efficient and accurate brain computer interfaces (BCIs). To the best of our knowledge, this is the first time the DDBP is recognized, defined, and addressed through the development of algorithmic solutions. The DASSO algorithms can be utilized in a variety of data mining and feature selection applications, in which finding discriminating structures across two datasets is of interest.

关键词： Signal processing algorithms Matrix decomposition Heuristic algorithms approximation algorithms Task analysis Electroencephalography Data mining Boolean matrix factorization (BMF) data mining feature selection brain-computer interfaces (BCIs) dynamic functional networks electroencephalography (EEG)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：