Gerault D.,LIMOS |
Minier M.,INSA Lyon |
Minier M.,French Institute for Research in Computer Science and Automation |
Solnon C.,INSA Lyon |
Solnon C.,French National Center for Scientific Research
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2016
In this paper, we introduce Constraint Programming (CP) models to solve a cryptanalytic problem: The chosen key differential attack against the standard block cipher AES. The problem is solved in two steps: In Step 1, bytes are abstracted by binary values; In Step 2, byte values are searched. We introduce two CP models for Step 1: Model 1 is derived from AES rules in a straightforward way; Model 2 contains new constraints that remove invalid solutions filtered out in Step 2. We also introduce a CP model for Step 2. We evaluate scale-up properties of two classical CP solvers (Gecode and Choco) and a hybrid SAT/CP solver (Chuffed). We show that Model 2 is much more efficient than Model 1, and that Chuffed is faster than Choco which is faster than Gecode on the hardest instances of this problem. Furthermore, we prove that a solution claimed to be optimal in two recent cryptanalysis papers is not optimal by providing a better solution. © Springer International Publishing Switzerland 2016.
Jachiet P.-A.,University Pierre and Marie Curie |
Pogorelcnik R.,LIMOS |
Berry A.,LIMOS |
Lopez P.,University Pierre and Marie Curie |
Bapteste E.,University Pierre and Marie Curie
Bioinformatics | Year: 2013
Motivation: Gene fusion is an important evolutionary process. It can yield valuable information to infer the interactions and functions of proteins. Fused genes have been identified as non-transitive patterns of similarity in triplets of genes. To be computationally tractable, this approach usually imposes an a priori distinction between a dataset in which fused genes are searched for, and a dataset that may have provided genetic material for fusion. This reduces the 'genetic space' in which fusion can be discovered, as only a subset of triplets of genes is investigated. Moreover, this approach may have a high-false-positive rate, and it does not identify gene families descending from a common fusion event.Results: We represent similarities between sequences as a network. This leads to an efficient formulation of previous methods of fused gene identification, which we implemented in the Python program FusedTriplets. Furthermore, we propose a new characterization of families of fused genes, as clique minimal separators of the sequence similarity network. This well-studied graph topology provides a robust and fast method of detection, well suited for automatic analyses of big datasets. We implemented this method in the C++ program MosaicFinder, which additionally uses local alignments to discard false-positive candidates and indicates potential fusion points. The grouping into families will help distinguish sequencing or prediction errors from real biological fusions, and it will yield additional insight into the function and history of fused genes. © 2013 The Author. Published by Oxford University Press. All rights reserved.
Blin L.,DeVry University |
Laforest C.,LIMOS |
Rovedakis S.,DeVry University |
Thibault N.,French National Center for Scientific Research
Computer Journal | Year: 2010
This paper is dedicated to the connection, by a provider, of multiple groups of nodes spread over a network. The role of the provider is to interconnect the members of every group. For this purpose, it must distribute the available links of the network between the groups. The general aim then is to allocate these links in such a way that the communications latencies in the allocated structure are equivalent to the ones in the original (full) network for each group. We study two approaches constructing structures preserving the maximum latency (called the diameter). Unfortunately we show that the associated optimization graph problems are difficult (one cannot be approximated by a constant and the other is NP-complete). Due to these difficulties we relax the constraint on the diameter and propose to construct a unique tree connecting all the groups together. We give a heuristic to treat this problem and we propose several analytical results on its maximum and average latencies performance. © 2009 The Author. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.
Caland F.,University of Lorraine |
Miron S.,University of Lorraine |
Brie D.,University of Lorraine |
IEEE Workshop on Statistical Signal Processing Proceedings | Year: 2011
A biosensor is a bacterium that is genetically modified to produce fluorescent proteins when exposed to environmental pollutants. In this paper, we investigate the possibility of estimating the concentration of environmental pollutants in a sample by using non-specific biosensors. To do that, we first propose an experimental procedure allowing to obtain three-way fluorescence data sets. The extraction of bio-sensor response to changes in environmental pollutant concentrations will be achieved by Candecomp/Parafac. This allows the estimation of multiple environmental pollutant concentrations using calibration curves of biosensors. © 2011 IEEE.
Battaia O.,LIMOS |
Delorme X.,LIMOS |
Dolgui A.,LIMOS |
Frederic G.,LIMOS |
Finel B.,Metz National School of Engineering
Proceedings of 2015 International Conference on Industrial Engineering and Systems Management, IEEE IESM 2015 | Year: 2015
Flow lines are widely used in mechanical industry. They consist to a set of workstations through which parts are manufactured. Designing such a line is a very complex problem due to manufacturing and design constraints and to the large number of possible decisions. Usually, the design of this type of production lines involves the selection of the necessary operations (indivisible units of work) to machine a part, the configuration design, the line scheduling. In this paper we present a survey of flow lines balancing problem, their approach and formulation and some solutions to optimize them studied in the literature. A special attention is paid for the assembly lines balancing problems. © 2015 International Institute for Innovation, Industrial Engineering and Entrepreneurship - I4e2.
RAIRO - Operations Research | Year: 2010
Let G = (V,E) be a simple undirected graph. A forest F ⊆ E of G is said to be clique-connecting if each tree of F spans a clique of G. This paper adresses the clique-connecting forest polytope. First we give a formulation and a polynomial time separation algorithm. Then we show that the nontrivial nondegenerate facets of the stable set polytope are facets of the clique-connecting polytope. Finally we introduce a family of rank inequalities which are facets, and which generalize the clique inequalities. © 2010 EDP Sciences, ROADEF, SMAI.