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

Backward pattern matching on Elastic-degenerate Strings

SN Computer Science 2023年第5期4卷 1-19页

作者： Procházka, Petr Cvacho, Ondřej Krčál, Luboš Holub, Jan Department of Theoretical Computer Science Faculty of Information Technology Czech Technical University in Prague Thákurova 2700/9 Prague 6 Czech Republic

The concept of elastic-degenerate strings (EDS) was introduced as a way of representing a sequenced population of the same species. Several online elastic-degenerate string matching (EDSM) algorithms were presented so far. Some of them provide a practical implementation. We propose a new on-line EDSM algorithm BNDM-EDS. Our algorithm combines two traditional algorithms BNDM and Shift-And that were adapted to the specificities needed by Elastic-degenerate Strings. BNDM-EDS is running in O(Nm⌈mw⌉) worst-case time. This implies O(Nm) time for small patterns, where m is the length of the searched pattern, N is the size of EDS, and w is the size of the computer word. The algorithm uses O(N+ n) space, where n is the length of EDS. BNDM-EDS requires a simple preprocessing step with time and space O(m) . We further present an extended version of the algorithm called BNDM-EDS-AA, which allows searching for proteins (amino acid sequences) encoded in DNA EDS. Though BNDM-EDS-AA considers more complex patterns than BNDM-EDS, it keeps its time and space efficiency. Experimental results on real genomic data show the superiority of BNDM-EDS over state-of-the-art algorithms. We also experimentally evaluate the efficiency of BNDM-EDS-AA for different pattern complexities, and evaluate the scaling of both BNDM-EDS and BNDM-EDS-AA with varying attributes of EDS datasets. © 2023, The Author(s).

关键词： degenerate pattern matching Elastic-degenerate strings Genomic sequences Pan-genomics

来源：评论

学校读者我要写书评

暂无评论

Backward pattern matching on Elastic degenerate Strings 12

Backward Pattern Matching on Elastic Degenerate Strings

引用

14th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC) / 12th International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS)

作者： Prochazka, Petr Cvacho, Ondrej Krcal, Lubos Holub, Jan Czech Tech Univ Fac Informat Technol Dep Theoret Comp Sci Thakurova 2700-9 Prague 6 Czech Republic

ISBN: (纸本)9789897584909

Recently, the concept of Elastic degenerate Strings (EDS) was introduced as a way of representing a sequenced population of the same species. Several on-line Elastic degenerate String matching (EDSM) algorithms were presented so far. Some of them provide practical implementation. We propose a new on-line EDSM algorithm BNDM-EDS. Our algorithm combines two traditional algorithms BNDM and the Shift-And that were adapted to the specifics needed by Elastic degenerate Strings. BNDM-EDS is running in O(Nmd[m/w]) worst-case time. This implies O (Nm) time for small patterns, where m is the length of the searched pattern, N is the size of EDS, and w is the size of the computer word. The algorithm uses O (N + n) space, where n is the length of EDS. BNDM-EDS requires a simple preprocessing step with time and space O (m). Experimental results on real genomic data show superiority of BNDM-EDS over state-of-the-art algorithms.

关键词： Elastic degenerate Strings Genomic Sequences degenerate pattern matching Pan-Genomics

来源：评论

学校读者我要写书评

暂无评论

On-line Searching in IUPAC Nucleotide Sequences 10

On-line Searching in IUPAC Nucleotide Sequences

引用

12th International Joint Conference on Biomedical Engineering Systems and Technologies / 10th International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS)

作者： Prochazka, Petr Holub, Jan Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Thakurova 2700-9 Prague 6 Czech Republic

ISBN: (纸本)9789897583537

We propose a novel pattern matching algorithm for consensus nucleotide sequences over IUPAC alphabet, called BADPM (Byte-Aligned degenerate pattern matching). The consensus nucleotide sequences represent a consensus obtained by sequencing a population of the same species and they are considered as so-called degenerate strings. BADPM works at the level of single bytes and it achieves sublinear search time on average. The algorithm is based on tabulating all possible factors of the searched pattern. It needs O (m + m alpha(2) logm)space data structure and O (m alpha(2)) time for preprocessing where m is a length of the pattern and a represents a maximum number of variants implied from a 4-gram over IUPAC alphabet. The worst-case locate time is bounded by O (nm(2)alpha(4)) for BADPM where n is the length of the input text. However, the experiments performed on real genomic data proved the sublinear search time. BADPM can easily cooperate with the block q-gram inverted index and so achieve still better locate time. We implemented two other pattern matching algorithms for IUPAC nucleotide sequences as a baseline: Boyer-Moore-Horspool (BMH) and Parallel Naive Search (PNS). Especially PNS proves its efficiency insensitive to the length of the searched pattern m. BADPM proved its strong superiority for searching middle and long patterns.

关键词： Consensus Nucleotide Sequences Genomic Sequences degenerate pattern matching q-gram Inverted Index

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：