Abstract

We investigate a dynamical complexity measure defined for finite automata with translucent letters (FAwtl). Roughly, this measure counts the minimal number of necessary jumps for such an automaton in order to accept an input. The model considered here is the deterministic finite automaton with translucent letters (DFAwtl). Unlike in the case of the nondeterministic variant, the function describing the jump complexity of any DFAwtl is either bounded by a constant or it is linear. We give a polynomial-time algorithm for deciding whether the jump complexity of a DFAwtl is constant-bounded or linear and we prove that the equivalence problem for DFAwtl of O(1) jump complexity is decidable. We also consider another fundamental problem for extensions of finite automata models, deciding whether the language accepted by a FAwtl is regular. We give a positive partial answer for DFAwtl over the binary alphabet, in contrast with the case of NFAwtl, where the problem is undecidable. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Abstract

Network biology is a powerful framework for studying the structure, function, and dynamics of biological systems, offering insights into the balance between health and disease states. The field is seeing rapid progress in all of its aspects: data availability, network synthesis, network analytics, and impactful applications in medicine and drug development. We review the most recent and significant results in network biomedicine, with a focus on the latest data, analytics, software resources, and applications in medicine. We also discuss what in our view are the likely directions of impactful development over the next few years.

Abstract

Abstract

We define the jump complexity of a finite automaton with translucent letters as a function that computes the smallest upper bound on the number of jumps needed by the automaton in order to accept each word of length n, for any positive integer n. We prove that a sufficient condition for a finite automaton with translucent letters to accept a regular language is to have a jump complexity bounded by a constant. Along the same lines, we show that there are languages which require a jump complexity in Omega(n) of any finite automaton with translucent letters accepting one of these languages. We also show that there exist nondeterministic finite automata with translucent letters of jump complexity in O(log n) and O(root n) that accept non-regular languages. Several open problems and directions for further developments are finally discussed.

Abstract

Abstract

BACKGROUND: Formalin-fixed, paraffin-embedded (FFPE) tissue slides are routinely used in cancer diagnosis, clinical decision-making, and stored in biobanks, but their utilization in Raman spectroscopy-based studies has been limited due to the background coming from embedding media.METHODS: Spontaneous Raman spectroscopy was used for molecular fingerprinting of FFPE tissue from 46 patient samples with known methylation subtypes. Spectra were used to construct tumor/non-tumor, IDH1WT/IDH1mut, and methylation-subtype classifiers. Support vector machine and random forest were used to identify the most discriminatory Raman frequencies. Stimulated Raman spectroscopy was used to validate the frequencies identified. Mass spectrometry of glioma cell lines and TCGA were used to validate the biological findings.RESULTS: Here we develop APOLLO (rAman-based PathOLogy of maLignant glioma) - a computational workflow that predicts different subtypes of glioma from spontaneous Raman spectra of FFPE tissue slides. Our novel APOLLO platform distinguishes tumors from nontumor tissue and identifies novel Raman peaks corresponding to DNA and proteins that are more intense in the tumor. APOLLO differentiates isocitrate dehydrogenase 1 mutant (IDH1mut) from wildtype (IDH1WT) tumors and identifies cholesterol ester levels to be highly abundant in IDHmut glioma. Moreover, APOLLO achieves high discriminative power between finer, clinically relevant glioma methylation subtypes, distinguishing between the CpG island hypermethylated phenotype (G-CIMP)-high and G-CIMP-low molecular phenotypes within the IDH1mut types.CONCLUSIONS: Our results demonstrate the potential of label-free Raman spectroscopy to classify glioma subtypes from FFPE slides and to extract meaningful biological information thus opening the door for future applications on these archived tissues in other cancers.

Abstract

Background. Formalin-fixed, paraffin-embedded (FFPE) tissue slides are routinely used in cancer diagnosis, clinical decision-making, and stored in biobanks, but their utilization in Raman spectroscopy-based studies has been limited due to the background coming from embedding media. Methods. Spontaneous Raman spectroscopy was used for molecular fingerprinting of FFPE tissue from 46 patient samples with known methylation subtypes. Spectra were used to construct tumor/non-tumor, IDH1(WT)/IDH1mut, and methylation-subtype classifiers. Support vector machine and random forest were used to identify the most discriminatory Raman frequencies. Stimulated Raman spectroscopy was used to validate the frequencies identified. Mass spectrometry of glioma cell lines and TCGA were used to validate the biological findings. Results. Here, we develop APOLLO (rAman-based PathOLogy of maLignant gliOma)-a computational workflow that predicts different subtypes of glioma from spontaneous Raman spectra of FFPE tissue slides. Our novel APOLLO platform distinguishes tumors from nontumor tissue and identifies novel Raman peaks corresponding to DNA and proteins that are more intense in the tumor. APOLLO differentiates isocitrate dehydrogenase 1 mutant (IDH1(mut)) from wild-type (IDH1(WT)) tumors and identifies cholesterol ester levels to be highly abundant in IDHmut glioma. Moreover, APOLLO achieves high discriminative power between finer, clinically relevant glioma methylation subtypes, distinguishing between the CpG island hypermethylated phenotype (G-CIMP)-high and G-CIMP-low molecular phenotypes within the IDH1(mut) types. Conclusions. Our results demonstrate the potential of label-free Raman spectroscopy to classify glioma subtypes from FFPE slides and to extract meaningful biological information thus opening the door for future applications on these archived tissues in other cancers.

Abstract

Abstract

We continue here the theoretical study initiated approximately twenty years ago on the possibility of using living cells for computing. In this paper, we reconsider the formal operations inspired by the intramolecular DNA rearrangements in the evolution of the macronucleus from the micronucleus in a group of ciliates. After introducing the concept of a valid string, we propose an efficient algorithm for checking this property for a given string. Then we investigate which of the considered operations preserve the property of a string to be valid. We also show that just one of the operations can be simulated by a finite transducer. The important problem regarding the order of applying the operations is then investigated showing that one operation can commute with the other two. Finally, we introduce the iterated variants and investigate a few properties. A sort of a normal form for the gene assembly in ciliates is obtained. The paper ends by a short discussion about open problems and further directions of research.

Abstract

We introduce an accepting splicing system based on a type of splicing, multiple splicing, which has never considered so far for accepting systems. This type of splicing differs from the usual operation in that several (not necessarily distinct) rules can be applied simultaneously to the same string. We first consider accepting multiple splicing systems where the number of splicing sites is a predefined constant. We prove that this model is computationally complete, if the constant is 2, by simulating a 2-tag system. Moreover, we show that the simulation is time-complexity preserving, and discuss also the descriptional complexity of the accepting splicing system given by our construction. We then consider the accepting multiple splicing systems where the number of sites has either an upper bound or a lower bound. The computational power of these systems is also investigated. We finally discuss some open problems. (C) 2022 The Author(s). Published by Elsevier B.V. on behalf of King Saud University.