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

An Efficient parallel Sketch-Based Algorithmic Workflow for Mapping Long Reads

IEEE TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2025年第1期22卷 13-26页

作者： Rahman, Tazin Bhowmik, Oieswarya Kalyanaraman, Ananth Washington State Univ Comp Sci & Engn Pullman WA 99163 USA Washington State Univ Sch Elect Engn & Comp Sci Pullman WA 99163 USA

Long read technologies are continuing to evolve at a rapid pace, with the latest of the high fidelity technologies delivering reads over 10 Kbp with high accuracy. Classical long read assemblers produce assemblies directly from long reads. Hybrid assembly workflows provide ways to combine partially constructed assemblies (or contigs) with newly sequenced long reads in order to generate genomic scaffolds. Under either setting, the main computational bottleneck is the step of mapping the long reads. While many tools implement the mapping step through overlap computations, designing alignment-free approaches is necessary for large-scale computations. In this paper, we visit the problem of mapping long reads to a database of subject sequences, in a fast and accurate manner. We present an efficient parallel algorithmic workflow, called JEM-mapper, that uses a new minimizer-based Jaccard estimator (or JEM) sketch to perform alignment-free mapping of long reads. For implementation and evaluation, we consider two application settings: (i) the hybrid scaffolding setting, which aims to map long reads to partial assemblies;and (ii) the classical long read assembly setting, which aims to map long reads to one another. We implemented an MPI+OpenMP version of JEM-mapper to enable parallelism at both distributed- and shared-memory layers. Experimental evaluation shows that JEM-mapper produces high-quality mapping while significantly improving the time to solution compared to state-of-the-art tools;e.g., in the hybrid setting for a large genome with 429 K HiFi long reads and 98K contigs, JEM-mapper produces a mapping with 99.41% precision and 97.91% recall, and 6.9x speedup over a state-of-the-art mapper.

关键词： Sequential analysis Accuracy Databases Pipelines Genomics parallel processing Hybrid power systems Bioinformatics Assembly Computational biology Alignment-free hybrid assembly long read mapping MinHashing parallel algorithms sketching

来源：评论

学校读者我要写书评

暂无评论

A Massively parallel SMC Sampler for Decision Trees

引用

algorithms 2025年第1期18卷 14-14页

作者： Drousiotis, Efthyvoulos Varsi, Alessandro Phillips, Alexander M. Maskell, Simon Spirakis, Paul G. Univ Liverpool Dept Elect Engn & Elect Liverpool L69 3GJ England UNIV LIVERPOOL Dept Comp Sci LIVERPOOL L69 3BX England

Bayesian approaches to decision trees (DTs) using Markov Chain Monte Carlo (MCMC) samplers have recently demonstrated state-of-the-art accuracy performance when it comes to training DTs to solve classification problems. Despite the competitive classification accuracy, MCMC requires a potentially long runtime to converge. A widely used approach to reducing an algorithm's runtime is to employ modern multi-core computer architectures, either with shared memory (SM) or distributed memory (DM), and use parallel computing to accelerate the algorithm. However, the inherent sequential nature of MCMC makes it unsuitable for parallel implementation unless the accuracy is sacrificed. This issue is particularly evident in DM architectures, which normally provide access to larger numbers of cores than SM. Sequential Monte Carlo (SMC) samplers are a parallel alternative to MCMC, which do not trade off accuracy for parallelism. However, the performance of SMC samplers in the context of DTs is underexplored, and the parallelization is complicated by the challenges in parallelizing its bottleneck, namely redistribution, especially on variable-size data types such as DTs. In this work, we study the problem of parallelizing SMC in the context of DTs both on SM and DM. On both memory architectures, we show that the proposed parallelization strategies achieve asymptotically optimal O(log2N) time complexity. Numerical results are presented for a 32-core SM machine and a 256-core DM cluster. For both computer architectures, the experimental results show that our approach has comparable or better accuracy than MCMC but runs up to 51 times faster on SM and 640 times faster on DM. In this paper, we share the GitHub link to the source code.

关键词： parallel algorithms machine learning Bayesian decision trees sequential Monte Carlo samplers Markov Chain Monte Carlo shared memory distributed memory

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for Testing Length Four Permutations 6

Parallel Algorithms for Testing Length Four Permutations

引用

6th International Symposium on parallel Architectures, algorithms, and Programming (PAAP)

作者： Han, Yijie Saxena, Sanjeev Univ Missouri Sch Comp & Engn Kansas City MO 64110 USA Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India

ISBN: (纸本)9781479938445

We present new parallel algorithms for testing pattern involvement for all length 4 permutations. Our algorithms have the complexity of O(log n) time with n/log n processors on the CREW PRAM model, O(log log log n) time with n/log log log n processors or constant time and n log 3 n processors on a CRCW PRAM model. parallel algorithms were not designed before for some of these patterns and for other patters the previous best algorithms require O(log n) time and n processors on the CREW PRAM model.

关键词： Separable permutations length 4 permutations pattern matching parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms of relative radiometric correction for images of TH-1 Satellite

Parallel algorithms of relative radiometric correction for i...

引用

18th China National Symposium on Remote Sensing - Remote Sensing of the Environment

作者： Wang Xiang Zhang Tingtao Cheng Jiasheng Yang Tao TH Satellite Ctr China Beijing 102102 Peoples R China Chinese Acad Sci Inst Elect Beijing 100091 Peoples R China

ISBN: (纸本)9781628411768

The first generation of transitive stereo-metric satellites in China, TH-1 Satellite, is able to gain stereo images of three-line-array with resolution of 5 meters, multispectral images of 10 meters, and panchromatic high resolution images of 2 meters. The procedure between level 0 and level 1A of high resolution images is so called relative radiometric correction (RRC for short). The processing algorithm of high resolution images, with large volumes of data, is complicated and time consuming. In order to bring up the processing speed, people in industry commonly apply parallel processing techniques based on CPU or GPU. This article firstly introduces the whole process and each step of the algorithm - that is in application - of RRC for high resolution images in level 0;secondly, the theory and characteristics of MPI (Message Passing Interface) and OpenMP (Open Multi-Processing) parallel programming techniques is briefly described, as well as the superiority for parallel technique in image processing field;thirdly, aiming at each step of the algorithm in application and based on MPI+OpenMP hybrid paradigm, the parallelizability and the strategies of parallelism for three processing steps: Radiometric Correction, Splicing Pieces of TDICCD (Time Delay Integration Charge-Coupled Device) and Gray Level Adjustment among pieces of TDICCD are deeply discussed, and furthermore, deducts the theoretical acceleration rates of each step and the one of whole procedure, according to the processing styles and independence of calculation;for the step Splicing Pieces of TDICCD, two different strategies of parallelism are proposed, which are to be chosen with consideration of hardware capabilities;finally, series of experiments are carried out to verify the parallel algorithms by applying 2-meter panchromatic high resolution images of TH-1 Satellite, and the experimental results are analyzed. Strictly on the basis of former parallel algorithms, the programs in the experiments are wri

关键词： TH-1 Satellite high resolution relative radiometric correction parallel algorithms MPI plus OpenMP

来源：评论

学校读者我要写书评

暂无评论

Probability algorithms for Data Statistics and Optimization Analysis of parallel Systems

Probability Algorithms for Data Statistics and Optimization ...

引用

International Conference on Computational Intelligence and Communication Networks (CICN)

作者： Xinyan Yu Faculty of Basic Sciences Teaching and Research Changchun Guanghua University Changchun China

ISBN: (数字)9798331505264

ISBN: (纸本)9798331505271

In the context of big data era, data processing and analysis are facing unprecedented challenges, especially the real-time processing and efficient analysis of massive data have become urgent problems. This study focuses on the parallelization and system optimization of probabilistic algorithms, aiming to improve the efficiency and accuracy of data processing by technical means. In terms of specific methods, we first deeply analyze where the bottlenecks of existing probabilistic algorithms lie when dealing with big data, and then design and implement an efficient parallelization framework. The framework makes full use of the computational power of multi-core processors, and realizes the parallelization of probabilistic algorithms through the strategies of task decomposition, data allocation and parallel execution. Meanwhile, we also optimize the system architecture, including resource scheduling, load balancing, and communication optimization, to ensure the stable operation and efficient execution of the parallelization algorithm. In our experiments, we selected several typical datasets for testing and compared the performance before and after parallelization. As the number of threads increases (from serial to 2-thread, 4-thread to 8-thread), the processing time is gradually shortened, which shows that parallel processing is very effective in accelerating computation. The method in this paper provides an efficient and reliable solution for big data processing and analysis, which helps to promote digital transformation and intelligent upgrading in various industries.

关键词： Accuracy Optimization methods Systems architecture Big Data Probabilistic logic Data processing Load management Resource management parallel algorithms Testing

来源：评论

学校读者我要写书评

暂无评论

Optimization of parallel implementation of UNRES package for coarse-grained simulations to treat large proteins

引用

JOURNAL OF COMPUTATIONAL CHEMISTRY 2023年第4期44卷 602-625页

作者： Sieradzan, Adam K. Sans-Duno, Jordi Lubecka, Emilia A. Czaplewski, Cezary Lipska, Agnieszka G. Ocetkiewicz, Krzysztof M. Proficz, Jerzy Czarnul, Pawel Krawczyk, Henryk Liwo, Adam Leszczyfiski, Henryk Univ Gdansk Fahrenheit Union Univ Gdansk Fac Chem Gdansk Poland Gdansk Univ Technol Fahrenheit Union Univ Gdansk Ctr Informat Tricity Acad Supercomp & Network CI Gdansk Poland Univ Lleida Dept Chem Lleida Spain Gdansk Univ Technol Fahrenheit Union Univ Gdansk Fac Elect Telecommun & Informat Gdansk Poland Univ Gdansk Fahrenheit Union Univ Gdansk Fac Math Phys & Informat Gdansk Poland

We report major algorithmic improvements of the UNRES package for physics-based coarse-grained simulations of proteins. These include (i) introduction of interaction lists to optimize computations, (ii) transforming the inertia matrix to a pentadiagonal form to reduce computing and memory requirements, (iii) removing explicit angles and dihedral angles from energy expressions and recoding the most time-consuming energy/force terms to minimize the number of operations and to improve numerical stability, (iv) using OpenMP to parallelize those sections of the code for which distributed-memory parallelization involves unfavorable computing/communication time ratio, and (v) careful memory management to minimize simultaneous access of distant memory sections. The new code enables us to run molecular dynamics simulations of protein systems with size exceeding 100,000 amino-acid residues, reaching over 1 ns/day (1 mu s/day in all-atom timescale) with 24 cores for proteins of this size. parallel performance of the code and comparison of its performance with that of AMBER, GROMACS and MARTINI 3 is presented.

关键词： coarse graining molecular dynamics OpenMP parallel algorithms UNRES

来源：评论

学校读者我要写书评

暂无评论

An adaptive enhancement method based on stochastic parallel gradient descent of glioma image

引用

IET IMAGE PROCESSING 2023年第14期17卷 3976-3985页

作者： Wang, Hongfei Peng, Xinhao Ma, ShiQing Wang, Shuai Xu, Chuan Yang, Ping Chinese Acad Sci Key Lab Adapt Opt Chengdu Peoples R China Chinese Acad Sci Inst Opt & Elect Chengdu Peoples R China Univ Chinese Acad Sci Sch Elect Elect & Commun Engn Beijing Peoples R China Univ Elect Sci & Technol China Sch Med Chengdu Peoples R China Univ Chinese Acad Sci Beijing Peoples R China Univ Elect Sci & Technol China Sichuan Prov Peoples Hosp Sichuan Acad Med Sci Dept Oncol Chengdu Sichuan Peoples R China Univ Elect Sci & Technol China Sichuan Prov Peoples Hosp Canc Inst Sichuan Acad Med Sci Chengdu Sichuan Peoples R China Univ Elect Sci & Technol China Sichuan Prov Peoples Hosp Dept Lab Med Chengdu Sichuan Peoples R China Univ Elect Sci & Technol China Sichuan Prov Peoples Hosp Sichuan Prov Key Lab Human Dis Gene Study Chengdu Sichuan Peoples R China

Brain tumour diagnosis is significant for both physicians and patients, but the low contrast and the artefacts of MRI glioma images always affect the diagnostic accuracy. The existing mainstream image enhancement methods are insufficient in improving contrast and suppressing artefacts simultaneously. To enrich the field of glioma image enhancement, this research proposed a glioma image enhancement method based on histogram modification and total variational using stochastic parallel gradient descent (SPGD) algorithm. Firstly, this method modifies the cumulative distribution function on the image histogram and performs gamma correction on the image according to the modified histogram to obtain a contrast-enhanced image. Then, the method suppresses the artefacts of glioma images by total variational and wavelet denoising algorithm. To get better enhancement images, the optimal parameters in the proposed method are searched by the SPGD algorithm. The statistical studies performed on 580 real glioma images demonstrate that the authors' approach can outperform the existing mainstream image enhancement methods. The results show that the proposed method increases the discrete entropy of the image by 8.9% and the contrast by 2.8% compared to original images. The enhanced images are produced by the proposed method with a natural appearance, appealing contrast, less degradation, and reasonable detail preservation. To enrich the field of glioma image enhancement, this paper proposed a glioma image enhancement framework based on histogram modification and total variational using stochastic parallel gradient descent (SPGD) algorithm. The results show that the proposed framework has superior performance compared to several existing glioma image enhancement methods. image

关键词： image denoising image enhancement parallel algorithms artefacts suppression contrast improvement histogram modification stochastic parallel gradient descent

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms FOR SOLVING STRUCTURAL INVERSE MAGNETOMETRY PROBLEM ON MULTICORE AND GRAPHIGS PROCESSORS 14

PARALLEL ALGORITHMS FOR SOLVING STRUCTURAL INVERSE MAGNETOME...

引用

14th International Multidisciplinary Scientific Geoconference (SGEM)

作者： Akimova, Elena N. Martyshko, Peter S. Misilov, Vladimir E. UB RAS Krasovskii Inst Math & Mech Ekaterinburg Russia UB RAS Bulashevich Inst Geophys Ekaterinburg Russia Yeltsin Ural Fed Univ Ekaterinburg Russia

ISBN: (纸本)9786197105100

The most important geophysical problems are inverse gravimetry and magnetometry problems. Among them are the structural gravimetry and magnetometry problems of finding interfaces between layers with different densities or magnetizations using known gravitational or magnetic data [1], [2], [3]. The gravimetry and magnetometry problems are described by nonlinear integral Fredholm equations of the first kind;they are ill-posed problems. After the discretization of integral operators, the problems are reduced to systems of nonlinear equations with dense matrices. The real gravity and magnetic measurements are carried out over a large area producing large-scale grids. Processing of gravity and magnetic data is time consuming and requires a lot of memory. In this paper, for solving the structural inverse magnetometry problem in a multilayer medium, efficient stable parallel algorithms based on iteratively regularized gradient methods with variable weight factors are proposed. The algorithms were implemented numerically with using new computing technologies on the parallel computing system Uran at the Institute of Mathematics and Mechanics of the UB RAS. The structural magnetometry problem with "quasi-model" data was solved.

关键词： gravimetry and magnetometry inverse problems parallel algorithms multicore and graphics processors

来源：评论

学校读者我要写书评

暂无评论

On the parallel Parameterized Complexity of MaxSAT Variants

引用

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 2023年 78卷 673-707页

作者： Bannach, Max Skambath, Malte Tantau, Till European Space Agcy Adv Concepts Team Noordwijk Netherlands Univ Kiel Dept Comp Sci Kiel Germany Univ Lubeck Inst Theoret Comp Sci Lubeck Germany

In the maximum satisfiability problem (MAX-SAT) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as possible. We study the parallel parameterized complexity of various versions of MAX-SAT and provide the first constant-time algorithms parameterized either by the solution size or by the allowed excess relative to some guarantee. For the dual parameterized version where the parameter is the number of clauses we are allowed to leave unsatisfied, we present the first parallel algorithm for MAX-2SAT (known as ALMOST-2SAT). The difficulty in solving ALMOST-2SAT in parallel comes from the fact that the iterative compression method, originally developed to prove that the problem is fixed-parameter tractable at all, is inherently sequential. We observe that a graph flow whose value is a parameter can be computed in parallel and develop a parallel algorithm for the vertex cover problem parameterized above the size of a given matching. Finally, we study the parallel complexity of MAX-SAT parameterized by the vertex cover number, the treedepth, the feedback vertex set number, and the treewidth of the input's incidence graph. While MAX-SAT is fixed parameter tractable for all of these parameters, we show that they allow different degrees of possible parallelization. For all four we develop dedicated parallel algorithms that are constructive, meaning that they output an optimal assignment - in contrast to results that can be obtained by parallel meta-theorems, which often only solve the decision version.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Massively parallel Circuit Setup in GPU-SPICE

引用

IEEE TRANSACTIONS ON COMPUTERS 2023年第8期72卷 2127-2138页

作者： van Santen, Victor M. Diep, Fu Lam Florian Henkel, Jorg Amrouch, Hussam Univ Stuttgart D-70569 Stuttgart Germany Karlsruhe Inst Technol KIT Chair Embedded Syst D-76133 Karlsruhe Germany

SPICE simulations are the industry standard to analyze circuits for decades. However, they are computationally complex as each circuit is simulated at the transistor-level where individual transistor is modeled with dozens of sophisticated equations. This limits the practicality of SPICE simulations to relatively small circuits. However, this is in a direct conflict with the ever-increasing demands of circuit designers in which SPICE simulations for large circuits (e.g., DSPs, AES, etc.) at full accuracy are inevitably required to fulfill new industrial standards like automotive safety ISO 26262 with tool confidence level 1. To accelerate SPICE simulation without sacrificing accuracy, state-of-the-art approaches have started to employ GPUs to parallelize the LU-factorization and device linearization phases. Instead of focusing on these phases, this article demonstrates for the first time that when large circuits come into play, a new and equally important performance bottleneck emerges at the circuit setup phase. Speeding up the circuit setup phase in SPICE is our key focus in this paper. Our two implementations demonstrate that our GPU-based circuit setup reduces the analysis time from 4.5 days to merely 89 seconds for a 256-bit multiplier, which consists of more than 1M transistors. Our achieved speedup is 4396x compared to the baseline (open-source NGSPICE) and more than 2x compared to commercial (HSPICE and Spectre) SPICE circuit setup.

关键词： SPICE simulation GPU parallel algorithms circuit setup circuit topology analysis radix SQL NGSPICE Xyce

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：