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

Precise feature selection using suffix array algorithm of bioinformatics

INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS 2025年 1-30页

作者： Zandvakili, Aboozar Javidi, Mohammad Masoud Mansouri, Najme Shahid Bahonar Univ Kerman Dept Comp Sci Kerman Iran Bahonar Univ Kerman Fac Shahid Kerman Iran

It is crucial to select the most relevant and informative features in a dataset to perform data analysis. Machine learning algorithms perform better when features are selected correctly. Feature selection is not solvable in polynomial time. The exact method takes exponential time, so the researchers used approximate algorithms to reach semi-optimal solutions. It is impossible to explore and exploit the search space in a balanced manner when using heuristic algorithms and metaheuristic methods. To solve this problem, the proposed method replaces meta-heuristic algorithms with the linear time SKEW algorithm in bioinformatics. First, each feature is ranked using the Pearson correlation criterion. Each feature is labeled A, C, G, or T according to its rank. The best feature is A, and the worst feature is T. The dataset can now be viewed as Deoxyribonucleic Acid (DNA). In the second step, the SKEW algorithm is used to determine the lexico-graphical order of suffixes. suffixes are considered and checked as selected features. The third step involves permuting the features, and the first and second steps are repeated. The best suffix with the lowest cost function is selected after multiple iterations (e.g., ten). As compared to Simulated Annealing (SA), Genetic Algorithm (GA), Gray Wolf Optimizer (GWO), Grasshopper Optimization Algorithm (GOA), Ant Colony Optimization (ACO), Greedy, Gravitational Search Algorithm (GSA), and Pyramid Gravitational Search Algorithm (PGSA), the proposed algorithm improves the objective function by 19.3%, 7.6%, 80.6%, 102.2%, 39.7%, 105.6%, 38.1%, and 14.2% respectively.

关键词： Feature selection Meta-heuristic suffix array Correlation

来源：评论

学校读者我要写书评

暂无评论

suffix array for multi-pattern matching with variable length wildcards

引用

INTELLIGENT DATA ANALYSIS 2021年第2期25卷 283-303页

作者： Liu, Na Xie, Fei Wu, Xindong Hefei Univ Technol Minist Educ Key Lab Knowledge Engn Big Data Hefei Anhui Peoples R China Hefei Univ Technol Sch Comp Sci & Informat Engn Hefei Anhui Peoples R China North Minzu Univ Sch Comp Sci & Engn Yinchuan Ningxia Peoples R China Hefei Normal Univ Dept Comp Sci & Technol Hefei 230009 Anhui Peoples R China Mininglamp Technol Mininglamp Acad Sci Beijing Peoples R China

Approximate multi-pattern matching is an important issue that is widely and frequently utilized, when the pattern contains variable-length wildcards. In this paper, two suffix array-based algorithms have been proposed to solve this problem. suffix array is an efficient data structure for exact string matching in existing studies, as well as for approximate pattern matching and multi-pattern matching. An algorithm called MMSA-S is for the short exact characters in a pattern by dynamic programming, while another algorithm called MMSA-L deals with the long exact characters by the edit distance method. Experimental results of Pizza & Chili corpus demonstrate that these two newly proposed algorithms, in most cases, are more time-efficient than the state-of-the-art comparison algorithms.

关键词： Pattern matching suffix array wildcards

来源：评论

学校读者我要写书评

暂无评论

suffix array and Lyndon factorization of a text

引用

JOURNAL OF DISCRETE ALGORITHMS 2014年第0期28卷 2-8页

作者： Mantaci, Sabrina Restivo, Antonio Rosone, Giovanna Sciortino, Marinella Univ Palermo Dipartimento Matemat & Informat Via Archirafi 34 I-90123 Palermo Italy

The main goal of this paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15] that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we propose sorts the suffixes by starting from the leftmost Lyndon factors, even if the whole text or the complete Lyndon factorization are not yet available. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Sorting suffixes BWT suffix array Lyndon word Lyndon factorization

来源：评论

学校读者我要写书评

暂无评论

Parallel and Space-Efficient Construction of Burrows-Wheeler Transform and suffix array for Big Genome Data

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2016年第3期13卷 592-598页

作者： Liu, Yongchao Hankeln, Thomas Schmidt, Bertil Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30332 USA Johannes Gutenberg Univ Mainz Inst Mol Genet D-55128 Mainz Germany Johannes Gutenberg Univ Mainz Inst Informat D-55128 Mainz Germany

Next-generation sequencing technologies have led to the sequencing of more and more genomes, propelling related research into the era of big data. In this paper, we present ParaBWT, a parallelized Burrows-Wheeler transform (BWT) and suffix array construction algorithm for big genome data. In ParaBWT, we have investigated a progressive construction approach to constructing the BWT of single genome sequences in linear space complexity, but with a small constant factor. This approach has been further parallelized using multi-threading based on a master-slave coprocessing model. After gaining the BWT, the suffix array is constructed in a memory-efficient manner. The performance of ParaBWT has been evaluated using two sequences generated from two human genome assemblies: the Ensembl Homo sapiens assembly and the human reference genome. Our performance comparison to FMD-index and Bwt-disk reveals that on 12 CPU cores, ParaBWT runs up to 2.2 x faster than FMD-index and up to 99.0 x faster than Bwt-disk. BWT construction algorithms for very long genomic sequences are time consuming and (due to their incremental nature) inherently difficult to parallelize. Thus, their parallelization is challenging and even relatively small speedups like the ones of our method over FMD-index are of high importance to research. ParaBWT is written in C++, and is freely available at http://***.

关键词： Burrows-Wheeler transform suffix array next-generation sequencing big data

来源：评论

学校读者我要写书评

暂无评论

Engineering a lightweight suffix array construction algorithm

引用

ALGORITHMICA 2004年第1期40卷 33-50页

作者： Manzini, G Ferragina, P Univ Piemonte Orientale Dipartimento Informat Alessandria Italy CNR IIT I-56100 Pisa Italy Univ Pisa Dipartimento Informat Pisa Italy

In this paper we describe a new algorithm for building the suffix array of a string. This task is equivalent to the problem of lexicographically sorting all the suffixes of the input string. Our algorithm is based on a new approach called deep-shallow sorting: we use a "shallow" sorter for the suffixes with a short common prefix, and a "deep" sorter for the suffixes with a long common prefix. All the known algorithms for building the suffix array either require a large amount of space or are inefficient when the input string contains many repeated substrings. Our algorithm has been designed to overcome this dichotomy. Our algorithm is "lightweight" in the sense that it uses very small space in addition to the space required by the suffix array itself. At the same time our algorithm is fast even when the input contains many repetitions: this has been shown by extensive experiments with inputs of size up to 110 Mb. The source code of our algorithm, as well as a C library providing a simple API, is available under the GNU GPL [26].

关键词： suffix array algorithmic engineering space-economical algorithms full-text index suffix tree

来源：评论

学校读者我要写书评

暂无评论

A taxonomy of suffix array construction algorithms

引用

ACM COMPUTING SURVEYS 2007年第2期39卷 1-31页

作者： Publisi, Simon J. Smyth, W. F. Turpin, Andrew H. RMIT Univ Sch Comp Sci & Informat Technol Melbourne Vic 3001 Australia Curtin Univ Technol Bentley WA 6102 Australia McMaster Univ Dept Comp & Software Algorithms Res Grp Hamilton ON L8S 4K1 Canada

In 1990, Manber and Myers proposed suffix arrays as a space-saving alternative to suffix trees and described the first algorithms for suffix array construction and use. Since that time, and especially in the last few years, suffix array construction algorithms have proliferated in bewildering abundance. This survey paper attempts to provide simple high-level descriptions of these numerous algorithms that highlight both their distinctive features and their commonalities, while avoiding as much as possible the complexities of implementation details. New hybrid algorithms are also described. We provide comparisons of the algorithms' worst-case time complexity and use of additional space, together with results of recent experimental test runs on many of their implementations.

关键词： algorithms design performance suffix array suffix tree suffix sorting Burrows-Wheeler transform

来源：评论

学校读者我要写书评

暂无评论

Two Efficient Algorithms for Linear Time suffix array Construction

引用

IEEE TRANSACTIONS ON COMPUTERS 2011年第10期60卷 1471-1484页

作者： Nong, Ge Zhang, Sen Chan, Wai Hong Sun Yat Sen Univ Dept Comp Sci Guangzhou 510275 Guangdong Peoples R China SUNY Coll Oneonta Dept Math Comp Sci & Stat Oneonta NY 13820 USA Hong Kong Inst Educ Dept Math & Informat Technol Hong Kong Hong Kong Peoples R China

We present, in this paper, two efficient algorithms for linear time suffix array construction. These two algorithms achieve their linear time complexities, using the techniques of divide-and-conquer, and recursion. What distinguish the proposed algorithms from other linear time suffix array construction algorithms (SACAs) are the variable-length leftmost S-type (LMS) substrings and the fixed-length d-critical substrings sampled for problem reduction, and the simple algorithms for sorting these sampled substrings: the induced sorting algorithm for the variable-length LMS substrings and the radix sorting algorithm for the fixed-length d-critical substrings. The very simple sorting mechanisms render our algorithms an elegant design framework, and, in turn, the surprisingly succinct implementations. The fully functional sample implementations of our proposed algorithms require only around 100 lines of C code for each, which is only 1/10 of the implementation of the KA [1] algorithm and comparable to that of the KS [2] algorithm. The experimental results demonstrate that these two newly proposed algorithms yield the best time and space efficiencies among all the existing linear time SACAs.

关键词： suffix array linear time divide-and-conquer

来源：评论

学校读者我要写书评

暂无评论

Extended suffix array construction using Lyndon factors

引用

SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES 2018年第8期43卷 1-9页

作者： Sunita Garg, Deepak Thapar Univ Comp Sci & Engn Patiala 147004 Punjab India Bennett Univ Comp Sci Engn Dept Greater Noida 201310 India

In this paper, we are extending the novel approach of incremental suffix array construction using Lyndon factorization to the construction of extended suffix array where extended suffix array is the suffix array along with the corresponding longest common prefix (LCP) array. Main motive behind the incremental and simultaneous construction of suffix array and LCP array is that both involve in calculating the order information by considering the common prefixes of the suffixes. As local suffixes once sorted have the same sorted order when these are merged with sorted suffixes of another Lyndon factor. So, merging of Lyndon factors is simply merging of two sorted lists of suffixes of these Lyndon factors. Also, the two sorted orders coincide thus making the merging of Lyndon factors a simple merging of two sorted lists of suffixes. Incremental LCP construction simultaneously saves a lot of computation and hence time. The proposed approach has quadratic run time and the disk working space requirement is O(n). Experiments also show the performance gain of our approach in terms of time over the existing method of incremental construction.

关键词： Computer science data structure suffix array Lyndon factors longest common prefix

来源：评论

学校读者我要写书评

暂无评论

Compact and hash based variants of the suffix array

引用

BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES 2017年第4期65卷 407-418页

作者： Grabowski, S. Raniszewski, M. Lodz Univ Technol Inst Appl Comp Sci 11 Politech Ave PL-90924 Lodz Poland

Full-text indexing aims at building a data structure over a given text capable of efficiently finding arbitrary text patterns, and possibly requiring little space. We propose two suffix array inspired full-text indexes. One, called SA-hash, augments the suffix array with a hash table to speed up pattern searches due to significantly narrowed search interval before the binary search phase. The other, called FBCSA, is a compact data structure, similar to Makinen's compact suffix array (MakCSA), but working on fixed size blocks. Experiments on the widely used Pizza & Chili datasets show that SA-hash is about 2-3 times faster in pattern searches (counts) than the standard suffix array, for the price of requiring 0.2n-1.1n bytes of extra space, where n is the text length. FBCSA, in one of the presented variants, reduces the suffix array size by a factor of about 1.5-2, while it gets close in search times, winning in speed with its competitors known from the literature, MakCSA and LCSA.

关键词： string matching full-text indexing suffix array compact indexes hashing

来源：评论

学校读者我要写书评

暂无评论

SaAlign: Multiple DNA/RNA sequence alignment and phylogenetic tree construction tool for ultra-large datasets and ultra-long sequences based on suffix array

引用

COMPUTATIONAL AND STRUCTURAL BIOTECHNOLOGY JOURNAL 2022年 20卷 1487-1493页

作者： Wang, Ziyuan Tan, Junjie Long, Yanling Liu, Yijia Lei, Wenyan Cai, Jing Yang, Yi Liu, Zhibin Sichuan Univ Coll Life Sci Key Lab Bioresource & Ecoenvironm Minist Educ Chengdu 610064 Sichuan Peoples R China Chongqing Med Univ Ctr Clin Mol MedChongqing Key Lab Pediat Natl Clin Res Ctr Child Hlth & DisordersChildren Minist EducKey Lab Child Dev & DisordersChina I Chongqing 400014 Peoples R China Sichuan Univ Coll Comp Sci Chengdu 610064 Sichuan Peoples R China Sichuan Univ West China Sch Pharm Chengdu 610041 Sichuan Peoples R China

Multiple DNA/RNA sequence alignment is an important fundamental tool in bioinformatics, especially for phylogenetic tree construction. With DNA-sequencing improvements, the amount of bioinformatics data is constantly increasing, and various tools need to be iterated constantly. Mitochondrial genome analyses of multiple individuals and species require bioinformatics software;therefore, their performances need to be optimized. To improve the alignment of ultra-large datasets and ultra-long sequences, we optimized a dynamic programming algorithm using longest common substring methods. Ultra-large test DNA datasets, containing sequences of different lengths, some over 300 kb (kilobase), revealed that the Multiple DNA/RNA Sequence Alignment Tool Based on suffix Tree (SaAlign) saved time and computational space. It outperformed the existing technical tools, including MAFFT and HAlign-II. For mitochondrial genome datasets having limited numbers of sequences, MAFFT performed the required tasks, but it could not handle ultra-large mitochondrial genome datasets for core dump error. We implement a multiple DNA/RNA sequence alignment tool based on Center Star strategy and use suffix array algorithm to optimize the spatial and time efficiency. Nowadays, whole-genome research and NGS technology are becoming more popular, and it is necessary to save computational resources for laboratories. That software is of great significance in these aspects, especially in the study of the whole-mitochondrial genome of plants. (C) 2022 The Authors. Published by Elsevier B.V. on behalf of Research Network of Computational and Structural Biotechnology.

关键词： Sequence analysis Alignment Phylogenetic tree suffix array

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：