1
|
Wu Y, Wang Y, Li Y, Zhu X, Wu X. Top-k Self-Adaptive Contrast Sequential Pattern Mining. IEEE TRANSACTIONS ON CYBERNETICS 2022; 52:11819-11833. [PMID: 34143749 DOI: 10.1109/tcyb.2021.3082114] [Citation(s) in RCA: 7] [Impact Index Per Article: 3.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/12/2023]
Abstract
For sequence classification, an important issue is to find discriminative features, where sequential pattern mining (SPM) is often used to find frequent patterns from sequences as features. To improve classification accuracy and pattern interpretability, contrast pattern mining emerges to discover patterns with high-contrast rates between different categories. To date, existing contrast SPM methods face many challenges, including excessive parameter selection and inefficient occurrences counting. To tackle these issues, this article proposes a top- k self-adaptive contrast SPM, which adaptively adjusts the gap constraints to find top- k self-adaptive contrast patterns (SCPs) from positive and negative sequences. One of the key tasks of the mining problem is to calculate the support (the number of occurrences) of a pattern in each sequence. To support efficient counting, we store all occurrences of a pattern in a special array in a Nettree, an extended tree structure with multiple roots and multiple parents. We employ the array to calculate the occurrences of all its superpatterns with one-way scanning to avoid redundant calculation. Meanwhile, because the contrast SPM problem does not satisfy the Apriori property, we propose Zero and Less strategies to prune candidate patterns and a Contrast-first mining strategy to select patterns with the highest contrast rate as the prefix subpattern and calculate the contrast rate of all its superpatterns. Experiments validate the efficiency of the proposed algorithm and show that contrast patterns significantly outperform frequent patterns for sequence classification. The algorithms and datasets can be downloaded from https://github.com/wuc567/Pattern-Mining/tree/master/SCP-Miner.
Collapse
|
2
|
Li Y, Yu L, Liu J, Guo L, Wu Y, Wu X. NetDPO: (delta, gamma)-approximate pattern matching with gap constraints under one-off condition. APPL INTELL 2022. [DOI: 10.1007/s10489-021-03000-2] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/17/2023]
|
3
|
Wu Y, Fan J, Li Y, Guo L, Wu X. NetDAP: (δ, γ) −approximate pattern matching with length constraints. APPL INTELL 2020. [DOI: 10.1007/s10489-020-01778-1] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/23/2022]
|
5
|
Mukherjee S, Barash D, Sengupta S. Comparative genomics and phylogenomic analyses of lysine riboswitch distributions in bacteria. PLoS One 2017; 12:e0184314. [PMID: 28873470 PMCID: PMC5584792 DOI: 10.1371/journal.pone.0184314] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/14/2017] [Accepted: 08/22/2017] [Indexed: 12/22/2022] Open
Abstract
Riboswitches are cis-regulatory elements that regulate the expression of genes involved in biosynthesis or transport of a ligand that binds to them. Among the nearly 40 classes of riboswitches discovered so far, three are known to regulate the concentration of biologically encoded amino acids glycine, lysine, and glutamine. While some comparative genomics studies of riboswitches focusing on their gross distribution across different bacterial taxa have been carried out recently, systematic functional annotation and analysis of lysine riboswitches and the genes they regulate are still lacking. We analyzed 2785 complete bacterial genome sequences to systematically identify 468 lysine riboswitches (not counting hits from multiple strains of the same species) and obtain a detailed phylogenomic map of gene-specific lysine riboswitch distribution across diverse prokaryotic phyla. We find that lysine riboswitches are most abundant in Firmicutes and Gammaproteobacteria where they are found upstream to both biosynthesis and/or transporter genes. They are relatively rare in all other prokaryotic phyla where if present they are primarily found upstream to operons containing many lysine biosynthesis genes. The genome-wide study of the genetic organisation of the lysine riboswitches show considerable variation both within and across different Firmicute orders. Correlating the location of a riboswitch with its genomic context and its phylogenetic relationship with other evolutionarily related riboswitch carrying species, enables identification and annotation of many lysine biosynthesis, transporter and catabolic genes. It also reveals previously unknown patterns of lysine riboswitch distribution and gene/operon regulation and allows us to draw inferences about the possible point of origin of lysine riboswitches. Additionally, evidence of horizontal transfer of riboswitches was found between Firmicutes and Actinobacteria. Our analysis provides a useful resource that will lead to a better understanding of the evolution of these regulatory elements and prove to be beneficial for exploiting riboswitches for developing targeted therapies.
Collapse
Affiliation(s)
- Sumit Mukherjee
- Department of Physical Sciences, Indian Institute of Science Education and Research Kolkata, Mohanpur, India
| | - Danny Barash
- Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
| | - Supratim Sengupta
- Department of Physical Sciences, Indian Institute of Science Education and Research Kolkata, Mohanpur, India
- * E-mail:
| |
Collapse
|
6
|
Rampášek L, Jimenez RM, Lupták A, Vinař T, Brejová B. RNA motif search with data-driven element ordering. BMC Bioinformatics 2016; 17:216. [PMID: 27188396 PMCID: PMC4870747 DOI: 10.1186/s12859-016-1074-x] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/29/2015] [Accepted: 05/07/2016] [Indexed: 01/30/2023] Open
Abstract
Background In this paper, we study the problem of RNA motif search in long genomic sequences. This approach uses a combination of sequence and structure constraints to uncover new distant homologs of known functional RNAs. The problem is NP-hard and is traditionally solved by backtracking algorithms. Results We have designed a new algorithm for RNA motif search and implemented a new motif search tool RNArobo. The tool enhances the RNAbob descriptor language, allowing insertions in helices, which enables better characterization of ribozymes and aptamers. A typical RNA motif consists of multiple elements and the running time of the algorithm is highly dependent on their ordering. By approaching the element ordering problem in a principled way, we demonstrate more than 100-fold speedup of the search for complex motifs compared to previously published tools. Conclusions We have developed a new method for RNA motif search that allows for a significant speedup of the search of complex motifs that include pseudoknots. Such speed improvements are crucial at a time when the rate of DNA sequencing outpaces growth in computing. RNArobo is available at http://compbio.fmph.uniba.sk/rnarobo. Electronic supplementary material The online version of this article (doi:10.1186/s12859-016-1074-x) contains supplementary material, which is available to authorized users.
Collapse
Affiliation(s)
- Ladislav Rampášek
- Department of Computer Science, University of Toronto, Toronto, M5R 3G4, ON, Canada.,Department of Pharmaceutical Sciences, Chemistry, and Molecular Biology and Biochemistry, University of California, Irvine, 2141 Natural Sciences 2, Irvine, 92697, CA, USA.,Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, Bratislava, 842 48, Slovakia
| | - Randi M Jimenez
- Department of Pharmaceutical Sciences, Chemistry, and Molecular Biology and Biochemistry, University of California, Irvine, 2141 Natural Sciences 2, Irvine, 92697, CA, USA
| | - Andrej Lupták
- Department of Pharmaceutical Sciences, Chemistry, and Molecular Biology and Biochemistry, University of California, Irvine, 2141 Natural Sciences 2, Irvine, 92697, CA, USA.
| | - Tomáš Vinař
- Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, Bratislava, 842 48, Slovakia
| | - Broňa Brejová
- Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, Bratislava, 842 48, Slovakia.
| |
Collapse
|
7
|
Mukherjee S, Sengupta S. Riboswitch Scanner: an efficient pHMM-based web-server to detect riboswitches in genomic sequences. Bioinformatics 2015; 32:776-8. [PMID: 26519506 DOI: 10.1093/bioinformatics/btv640] [Citation(s) in RCA: 35] [Impact Index Per Article: 3.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/09/2015] [Accepted: 10/25/2015] [Indexed: 11/13/2022] Open
Abstract
UNLABELLED Riboswitches are non-coding RNA located in the 5' untranslated regions where they bind a target metabolite used to specify the riboswitch class and control the expression of associated genes. Accurate identification of riboswitches is the first step towards understanding their regulatory and functional roles in the cell. In this article, we describe a new web application named Riboswitch Scanner which provides an automated pipeline for pHMM-based detection of riboswitches in partial as well as complete genomic sequences rapidly, with high sensitivity and specificity. AVAILABILITY AND IMPLEMENTATION Riboswitch Scanner can be freely accessed on the web at http://service.iiserkol.ac.in/∼riboscan/ CONTACT mukherjee.sumit89@gmail.com SUPPLEMENTARY INFORMATION Supplementary data are available at Bioinformatics online.
Collapse
Affiliation(s)
- Sumit Mukherjee
- Department of Physical Sciences, Indian Institute of Science Education and Research Kolkata, Mohanpur-741246, West Bengal, India
| | - Supratim Sengupta
- Department of Physical Sciences, Indian Institute of Science Education and Research Kolkata, Mohanpur-741246, West Bengal, India
| |
Collapse
|
8
|
Nucleic Acid Aptamers: An Emerging Tool for Biotechnology and Biomedical Sensing. SENSORS 2015; 15:16281-313. [PMID: 26153774 PMCID: PMC4541879 DOI: 10.3390/s150716281] [Citation(s) in RCA: 103] [Impact Index Per Article: 11.4] [Reference Citation Analysis] [Abstract] [Key Words] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 04/25/2015] [Revised: 06/26/2015] [Accepted: 06/30/2015] [Indexed: 02/06/2023]
Abstract
Detection of small molecules or proteins of living cells provides an exceptional opportunity to study genetic variations and functions, cellular behaviors, and various diseases including cancer and microbial infections. Our aim in this review is to give an overview of selected research activities related to nucleic acid-based aptamer techniques that have been reported in the past two decades. Limitations of aptamers and possible approaches to overcome these limitations are also discussed.
Collapse
|