International audience

The identification of essential genes has garnered considerable attention from researchers in recent years. This process of identification uncovers minimal functional modules that enable the survival of an organism, making it of paramount importance in the fields of biomedicine and biotechnology. To address this challenging issue, computational methods have become increasingly utilized to complement experimental approaches, which tend to be intricate and costly. Various classifiers, based on the selection of feature sets, have been proposed and have shown promising results thus far. In this paper, leveraging 50 sulfate reducing bacteria (SRB) organisms - microbes frequently associated with biofilm formation, biofilm-driven corrosion, and complex microbial community dynamics; we aim to show that classifiers can achieve very good performance using only a minimal set of relevant features. Specifically, we demonstrate that classifier performance can be improved by considering minimal relevant features while taking into account the taxonomy of different organisms. A total of 37,500 features were generated from nucleotide and protein sequences of 41 SRB organisms to construct a machine learning model system aimed at predicting essential genes. Our feature engineering module identified 58 subsets of features. Through cross-validation, we achieved competitive intra-organism prediction performance. The best models obtained had an AUC of 0.99, precision of 0.99, recall of 0.99, and an F1-score of 0.99. Subsequently, this system was used to perform extra-organism (new organism not seen by the model) validation using nine left-out SRB organisms. The results obtained for these test organisms demonstrated the efficacy of our models with maximum precision, maximum recall, maximum F1-score, and maximum AUC equal to 0.99,$0.99,0.99$, and 0.97, respectively. Our approach has significantly outperformed previously proposed methods in terms of average metrics, indicating better generalization of the models. Finally, this approach allows researchers to evaluate the predicted result in the lab with fewer variables to consider in their experimental design.

International audience

The task of mining gradual itemsets holds significant importance in pattern mining, particularly when working with numerical data. It involves the discovery of covariations between attributes in the form of “The more/less X,…, the more/less Y,” referred to as gradual itemsets. However, discovering these itemsets remains challenging, partly due to the exponential combinatorial search space involved in large-scale data processing. Consequently, existing algorithms for gradual itemset mining encounter difficulties, such as slow processing speeds, and occasional failures to terminate due to the overwhelming number of candidate itemsets requiring exploration. A large number of candidates is generated, but a large proportion of them turns out to be infrequent once their supports are computed. This paper introduces an approach to streamline this process by efficiently reducing the number of candidates for which support needs to be computed through the introduction of a stricter upper-bound criterion. By circumventing the costly support computation for numerous candidate itemsets, our approach exhibits efficiency in terms of speed when applied to real databases, including large-scale databases that pose challenges for existing algorithms. Furthermore, we establish a connection in terms of pattern coverage between the two principal gradualness semantics commonly employed in the literature.

International audience

In this paper, we address the issue of mining seasonal gradual patterns, which consists in identifying attribute co-variations in the form "when X increases/decreases, Y in-creases/decreases", that seasonally appear in data ("X and Y co-increase from March to June in more than 75% of the observed years"). Such kind of patterns has recently emerged for analyzing the sequences of temporal data and some algorithms have been proposed to automatically extract these patterns from numerical data. However, mining seasonal gradual patterns remains very challenging as the task is more complex than extracting gradual patterns in a simple sequence. In fact, one can note that extracting gradual patterns frequently appearing over a precise period of time (season) amounts to extracting, for each season, the gradual patterns common to multiple sequences. From this observation, we propose an algorithm to extract seasonal gradual patterns from temporal data sequences which exploits closed frequent itemsets mining algorithms to perform a search season by season. Experimental results obtained on a real world dataset show that compared to state-of-the-art algorithms, our proposed algorithm is efficient and can extract the complete set of frequent (closed) seasonal gradual patterns from the sequences of temporal numerical data.

Gradual itemsets model complex attributes covariations of the form the more or less is A, the more or less is B. Recently, such kind of itemsets has received great attention over the last years, and several proposals have been introduced to automatically extract these patterns from numerical databases. Unfortunately, discovering such itemsets remains challenging because of the exponential combinatorial search space.In this paper, we first formalize the problem of mining gradual itemsets as a constraint-based problem. Then, we use SAT solvers for solving the corresponding propositional satisfiability problem. Extensive experiments on real-world datasets confirm that our proposal is competitive with GRITE, one of the most efficient state-of-the-art algorithm for discovering frequent gradual itemsets. Lastly, we show the flexibility of our SAT-based approach by its ability to modeling additional user constraints without revising the solving process.

Mining frequent simultaneous attribute co-variations in numerical databases is also called frequent gradual pattern problem. Few efficient algorithms for automatically extracting such patterns have been reported in the literature. Their main difference resides in the variation semantics used. However in applications with temporal order relations, those algorithms fail to generate correct frequent gradual patterns as they do not take this temporal constraint into account in the mining process. In this paper, we propose an approach for extracting frequent gradual patterns for which the ordering of supporting objects matches the temporal order. This approach considerably reduces the number of gradual patterns within an ordered data set. The experimental results show the benefits of our approach.

Gradual itemsets model complex attributes covariation of the form "The more or less is A, the more or less is B". Recently, such kind of itemsets have received attention from the data mining community, where several formalizations and methods have been defined to automatically extract and maintain gradual patterns from numerical databases. However, mining gradual itemsets remains challenging as the task is more complex than ordering the transactions according to several dimensions or attributes. In fact, the order in which attributes are considered impacts the sorting operation. One can note that an ordering of the transactions according to a single attribute leads to a sequence of itemsets where items correspond to transaction identifiers. In this paper and from this observation, we propose a new formulation of the gradual itemset mining task as the problem of sequential pattern mining. This original reduction allows us to exploit sequential pattern mining algorithms to extract gradual itemsets. Experimental results obtained on several numerical datasets show the feasibility of our proposed framework.

Gradual patterns that capture the order correlations of the form "The more/less X, then the more/less Y" play an important role in many real world applications. In this paper, we propose an approach for extracting (closed) frequent gradual patterns when the ordering of supporting objects matches the temporal order. This approach allows to reduce the quantity of mined patterns when the objects follow a temporal order relation. The experimental results obtained on the paleoecological data show the efficiency of our approach and the interpretation of those results bring new knowledge to paleoecological experts.

Conflict based clause learning is known to be an important component in Modern SAT solving. Because of the exponential blow up of the size of learnt clauses database, maintaining a relevant and polynomially bounded set of learnt clauses is crucial for the efficiency of clause learning based SAT solvers. In this paper, we first compare several criteria for selecting the most relevant learnt clauses with a simple random selection strategy. We then propose new criteria allowing us to select relevant clauses w.r.t. A given search state. Then, we use such strategies as a means to diversify the search in a portfolio based parallel solver. An experimental evaluation comparing the classical Many SAT solver with the one augmented with multiple deletion strategies, shows the interest of such approach.

This paper presents a dynamic substitution technique of Boolean functions. It first recovers a set of Boolean functions from Boolean formula in conjunctive normal form (CNF). Then these functions are used to reduce the size of the learnt clauses by substituting the input arguments by the output ones. Preliminary experiments show the feasibility of our approach on some classes of SAT instances taken from the recent SAT Race and competitions.