Pasar al contenido principal

METODOS FORMALES ESCALABLES PARA APLICACIONES EN ENTORNOS REALES

PID2021-122830OB-C43

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2021
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 19
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Evolutionary trajectories of new duplicated and putative de novo genes

  • Montañés, José Carlos
  • Huertas, Marta
  • Messeguer, Xavier
  • Albà Soler, Mar
The formation of new genes during evolution is an important motor of functional innovation, but the rate at which new genes originate and the likelihood that they persist over longer evolutionary periods are still poorly understood questions. Two important mechanisms by which new genes arise are gene duplication and de novo formation from a previously noncoding sequence. Does the mechanism of formation influence the evolutionary trajectories of the genes? Proteins arisen by gene duplication retain the sequence and structural properties of the parental protein, and thus they may be relatively stable. Instead, de novo originated proteins are often species specific and thought to be more evolutionary labile. Despite these differences, here we show that both types of genes share a number of similarities, including low sequence constraints in their initial evolutionary phases, high turnover rates at the species level, and comparable persistence rates in deeper branchers, in both yeast and flies. In addition, we show that putative de novo proteins have an excess of substitutions between charged amino acids compared with the neutral expectation, which is reflected in the rapid loss of their initial highly basic character. The study supports high evolutionary dynamics of different kinds of new genes at the species level, in sharp contrast with the stability observed at later stages., We acknowledge funding from Ministerio de Ciencia e Innovación Agencia Estatal de Investigación grant PGC2018-094091-B-I00 (cofunded by Fondo Europeo de Desarrollo Regional), as well as grants PID2021-122726NB-I00 and PID2021-122830OB-C43 funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”, by the “European Union”. We also acknowledge funding from Generalitat de Catalunya, grant 2021SGR00042. The work was also funded by the European Union (ERC, NovoGenePop, project number 101052538). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Speeding up pseudo-Boolean propagation

  • Nieuwenhuis, Robert Lukas Mario|||0000-0002-6489-2138
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
  • Zhao, Rui|||0000-0002-1796-0062
Unit propagation is known to be one of the most time-consuming procedures inside CDCL-based SAT solvers. Not surprisingly, it has been studied in depth and the two-watched-literal scheme, enhanced with implementation details boosting its performance, has emerged as the dominant method. In pseudo-Boolean solvers, the importance of unit propagation is similar, but no dominant method exists: counter propagation and watched-based extensions are efficient for different types of constraints, which has opened the door to hybrid methods. However, probably due to the higher complexity of implementing pseudo-Boolean solvers, research efforts have not focused much on concrete implementation details for unit propagation but rather on higher-level aspects of other procedures, such as conflict analysis. In this paper, we present (i) a novel methodology to precisely assess the performance of propagation mechanisms, (ii) an evaluation of implementation variants of the propagation methods present in RoundingSat and (iii) a detailed analysis showing that hybrid methods outperform the ones based on a single technique. Our final contribution is to show that a carefully implemented hybrid propagation method is considerably faster than the preferred propagation mechanism in RoundingSat, and that this improvement leads to a better overall performance of the solver., All authors are supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”. Second and third authors are supported by Barcelogic through research grants C-11423 and C-11422, respectively., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On learning when to decompose graphical models

  • Petrova, Aleksandra
  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
Decomposition is a well-known algorithmic technique for Graphical Models. It is commonly believed that such a technique is cost-effective for instances with low width. In this paper, we show on a large data set of real-life inspired instances that this is not the case. To better understand this result, we narrow our study and consider k-tree instances where the width is well controlled and get similar results. Finally, we show that by adding a few simple features and using simple Machine Learning models we can predict the convenience to decompose with an accuracy of more than 85%, which produces time reductions in standard benchmarks of nearly 90%., Supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Symbolic conflict analysis in pseudo-Boolean optimization

  • Nieuwenhuis, Robert Lukas Mario|||0000-0002-6489-2138
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
  • Zhao, Rui|||0000-0002-1796-0062
In the the last two decades, a lot of effort has been devoted to the development of satisfiability-checking tools for a variety of SAT-related problems. However, most of these tools lack optimization capabilities. That is, instead of finding any solution, one is sometimes interested in a solution that is best according to some criterion. Pseudo-Boolean solvers can be used to deal with optimization by successively solving a series of problems that contain an additional pseudo-Boolean constraint expressing that a better solution is required. A key point for the success of this simple approach is that lemmas that are learned for one problem can be reused for subsequent ones. In this paper we go one step further and show how, by using a simple symbolic conflict analysis procedure, not only can lemmas be reused between problems but also strengthened, thus further pruning the search space traversal. In addition, we show how this technique automatically allows one to infer upper bounds in maximization problems, thus giving an estimation of how far the solver is from finding an optimal solution. Experimental results with our PB solver reveal that (i) this technique is indeed effective in practice, providing important speedups in problems where several solutions are found and (ii) on problems with very few solutions, where the impact of our technique is limited, its overhead is negligible., All authors are supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”. Second and third authors are supported by Barcelogic through research grants C-11423 and C-11422, respectively., Peer Reviewed, 9 - Indústria, Innovació i Infraestructura
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Improving and understanding the power of satisfaction-driven clause learning

  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Li, Chunxiao
  • Wu, Darryl
  • Chung, Jonathan
  • Ganesh, Vijay
In this paper, we explain how to improve Satisfaction-Driven Clause Learning (SDCL) SAT solvers by using a MaxSAT-based technique that enables them to learn shorter, and hence better, redundant clauses. A thorough empirical evaluation of an implementation on the MapleSAT solver shows that the resulting system solves Mutilated Chess Board (MCB) problems significantly faster than CDCL solvers, without requiring any alteration to the branching heuristic used by the underlying CDCL SAT solver. Additionally we improve the understanding of the power of these solvers by proving that, given a refutation of a formula that consists of resolution and redundant-clause addition steps, an SDCL solver is able to produce a proof whose size is polynomial with respect to the size of the original refutation., Albert Oliveras is supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 andby “ERDF: A way of making Europe”., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Theoretical and empirical analysis of cost-function merging for implicit hitting set WCSP solving

  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Rollón Rico, Emma|||0000-0001-8021-9464
The Implicit Hitting Set (HS) approach has shown very effective for MaxSAT solving. However, only preliminary promising results have been obtained for the very similar Weighted CSP framework. In this paper we contribute towards both a better theoretical understanding of the HS approach and a more effective HS-based solvers for WCSP. First, we bound the minimum number of iterations of HS thanks to what we call distinguished cores. Then, we show a source of inefficiency by introducing two simple problems where HS is unfeasible. Next, we propose two reformulation methods that merge cost-functions to overcome the problem. We provide a theoretical analysis that quantifies the magnitude of the improvement of each method with respect to the number of iterations of the algorithm. In particular, we show that the reformulations can bring an exponential number of iterations down to a constant number in our working examples. Finally, we complement our theoretical analysis with two sets of experiments. First, we show that our results are aligned with real executions. Second, and most importantly, we conduct experiments on typical benchmark problems and show that cost-function merging may be heuristically applied and it may accelerate HS algorithms by several orders of magnitude. In some cases, it even outperforms state-of-the-art solvers., The work of Javier Larrosa and Emma Rollon was supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”. The work of Conrado Martínez was supported by grant PID2020-112581GB-C21 (MOTION Project), funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Learning shorter redundant clauses in SDCL using MaxSAT

  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Li, Chunxiao
  • Wu, Darryl
  • Chung, Jonathan
  • Ganesh, Vijay
In this paper we present the design and implementation of a Satisfaction-Driven Clause Learning (SDCL) SAT solver, MapleSDCL, which uses a MaxSAT-based technique that enables it to learn shorter, and hence better, redundant clauses. We also perform a thorough empirical evaluation of our method and show that our SDCL solver solves Mutilated Chess Board (MCB) problems significantly faster than CDCL solvers, without requiring any alteration to the branching heuristic used by the underlying CDCL SAT solver., Albert Oliveras: Supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Using execution logs for improving pseudo-Boolean propagation

  • Nieuwenhuis, Robert Lukas Mario|||0000-0002-6489-2138
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
  • Zhao, Rui|||0000-0002-1796-0062
Among all procedures that CDCL-based SAT solvers implement, unit propagation dominates the total running time. Hence, it is not a surprise that large research efforts have been invested on improving it. As a result, the two-watched-literal scheme, enhanced with implementation details boosting its performance, emerged as the dominant method. The importance of unit propagation in pseudo-Boolean solvers is similar. However, no dominant method exists: counter and watch-based propagation are well-suited for different types of constraints, opening the door to hybrid methods. The higher complexity of implementing pseudo-Boolean solvers has shifted the research focus to higher-level aspects of other procedures, considering implementation details of unit propagation not a priority. In this paper, we first present execution logs: a novel methodology that allows us to precisely evaluate the performance of different propagation procedures. Secondly, we show how both counter and watch-based propagation routines in the RoundingSat solver can be largely improved thanks to a careful analysis of various implementation issues. Thirdly, a detailed analysis shows that hybrid methods outperform the ones based on a single technique. Finally, our experiments reveal that improvements in propagation lead to a clearly better overall performance of the solver., All authors are supported by grant PID2021-122830OB-C43, funded by project MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”, and by grant PID2024-157044OB-C32, funded by MICIU /AEI /10.13039/501100011033 / FEDER, UE. Second and third authors are supported by Barcelogic through research grants C-11423 and C-11422, respectively., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Learning shorter redundant clauses in SDCL using MaxSAT

  • Oliveras Llunell, Albert
  • Li, Chunxiao
  • Wu, Darryl
  • Chung, Jonathan
  • Ganesh, Vijay
In this paper we present the design and implementation of a Satisfaction-Driven Clause Learning (SDCL) SAT solver, MapleSDCL, which uses a MaxSAT-based technique that enables it to learn shorter, and hence better, redundant clauses. We also perform a thorough empirical evaluation of our method and show that our SDCL solver solves Mutilated Chess Board (MCB) problems significantly faster than CDCL solvers, without requiring any alteration to the branching heuristic used by the underlying CDCL SAT solver., Albert Oliveras: Supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Theoretical and empirical analysis of cost-function merging for implicit hitting set WCSP solving

  • Larrosa Bondia, Francisco Javier
  • Martínez Parra, Conrado
  • Rollón Rico, Emma
The Implicit Hitting Set (HS) approach has shown very effective for MaxSAT solving. However, only preliminary promising results have been obtained for the very similar Weighted CSP framework. In this paper we contribute towards both a better theoretical understanding of the HS approach and a more effective HS-based solvers for WCSP. First, we bound the minimum number of iterations of HS thanks to what we call distinguished cores. Then, we show a source of inefficiency by introducing two simple problems where HS is unfeasible. Next, we propose two reformulation methods that merge cost-functions to overcome the problem. We provide a theoretical analysis that quantifies the magnitude of the improvement of each method with respect to the number of iterations of the algorithm. In particular, we show that the reformulations can bring an exponential number of iterations down to a constant number in our working examples. Finally, we complement our theoretical analysis with two sets of experiments. First, we show that our results are aligned with real executions. Second, and most importantly, we conduct experiments on typical benchmark problems and show that cost-function merging may be heuristically applied and it may accelerate HS algorithms by several orders of magnitude. In some cases, it even outperforms state-of-the-art solvers., The work of Javier Larrosa and Emma Rollon was supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”. The work of Conrado Martínez was supported by grant PID2020-112581GB-C21 (MOTION Project), funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Speeding up pseudo-Boolean propagation

  • Nieuwenhuis, Robert Lukas Mario
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
  • Zhao, Rui
Unit propagation is known to be one of the most time-consuming procedures inside CDCL-based SAT solvers. Not surprisingly, it has been studied in depth and the two-watched-literal scheme, enhanced with implementation details boosting its performance, has emerged as the dominant method. In pseudo-Boolean solvers, the importance of unit propagation is similar, but no dominant method exists: counter propagation and watched-based extensions are efficient for different types of constraints, which has opened the door to hybrid methods. However, probably due to the higher complexity of implementing pseudo-Boolean solvers, research efforts have not focused much on concrete implementation details for unit propagation but rather on higher-level aspects of other procedures, such as conflict analysis. In this paper, we present (i) a novel methodology to precisely assess the performance of propagation mechanisms, (ii) an evaluation of implementation variants of the propagation methods present in RoundingSat and (iii) a detailed analysis showing that hybrid methods outperform the ones based on a single technique. Our final contribution is to show that a carefully implemented hybrid propagation method is considerably faster than the preferred propagation mechanism in RoundingSat, and that this improvement leads to a better overall performance of the solver., All authors are supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”. Second and third authors are supported by Barcelogic through research grants C-11423 and C-11422, respectively., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Symbolic conflict analysis in pseudo-Boolean optimization

  • Nieuwenhuis, Robert Lukas Mario
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
  • Zhao, Rui
In the the last two decades, a lot of effort has been devoted to the development of satisfiability-checking tools for a variety of SAT-related problems. However, most of these tools lack optimization capabilities. That is, instead of finding any solution, one is sometimes interested in a solution that is best according to some criterion. Pseudo-Boolean solvers can be used to deal with optimization by successively solving a series of problems that contain an additional pseudo-Boolean constraint expressing that a better solution is required. A key point for the success of this simple approach is that lemmas that are learned for one problem can be reused for subsequent ones. In this paper we go one step further and show how, by using a simple symbolic conflict analysis procedure, not only can lemmas be reused between problems but also strengthened, thus further pruning the search space traversal. In addition, we show how this technique automatically allows one to infer upper bounds in maximization problems, thus giving an estimation of how far the solver is from finding an optimal solution. Experimental results with our PB solver reveal that (i) this technique is indeed effective in practice, providing important speedups in problems where several solutions are found and (ii) on problems with very few solutions, where the impact of our technique is limited, its overhead is negligible., All authors are supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”. Second and third authors are supported by Barcelogic through research grants C-11423 and C-11422, respectively., Peer Reviewed, 9 - Indústria, Innovació i Infraestructura, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Analyzing multiple conflicts in SAT: an experimental evaluation

  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
  • Zhao, Rui
Unit propagation and conflict analysis are two essential ingredients of CDCL SAT Solving. The order in which unit propagation is computed does not matter when no conflict is found, because it is well known that there exists a unique unit-propagation fixpoint. However, when a conflict is found, current CDCL implementations stop and analyze that concrete conflict, even though other conflicts may exist in the unit-propagation closure. In this experimental evaluation, we report on our experience in modifying this concrete aspect in the CaDiCaL SAT Solver and try to answer the question of whether we can improve the performance of SAT Solvers by the analysis of multiple conflicts., All authors are supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Improving and understanding the power of satisfaction-driven clause learning

  • Oliveras Llunell, Albert
  • Li, Chunxiao
  • Wu, Darryl
  • Chung, Jonathan
  • Ganesh, Vijay
In this paper, we explain how to improve Satisfaction-Driven Clause Learning (SDCL) SAT solvers by using a MaxSAT-based technique that enables them to learn shorter, and hence better, redundant clauses. A thorough empirical evaluation of an implementation on the MapleSAT solver shows that the resulting system solves Mutilated Chess Board (MCB) problems significantly faster than CDCL solvers, without requiring any alteration to the branching heuristic used by the underlying CDCL SAT solver. Additionally we improve the understanding of the power of these solvers by proving that, given a refutation of a formula that consists of resolution and redundant-clause addition steps, an SDCL solver is able to produce a proof whose size is polynomial with respect to the size of the original refutation., Albert Oliveras is supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 andby “ERDF: A way of making Europe”., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Evolutionary trajectories of new duplicated and putative de novo genes

  • Montañés, José Carlos
  • Huertas, Marta
  • Messeguer, Xavier
  • Albà Soler, Mar
The formation of new genes during evolution is an important motor of functional innovation, but the rate at which new genes originate and the likelihood that they persist over longer evolutionary periods are still poorly understood questions. Two important mechanisms by which new genes arise are gene duplication and de novo formation from a previously noncoding sequence. Does the mechanism of formation influence the evolutionary trajectories of the genes? Proteins arisen by gene duplication retain the sequence and structural properties of the parental protein, and thus they may be relatively stable. Instead, de novo originated proteins are often species specific and thought to be more evolutionary labile. Despite these differences, here we show that both types of genes share a number of similarities, including low sequence constraints in their initial evolutionary phases, high turnover rates at the species level, and comparable persistence rates in deeper branchers, in both yeast and flies. In addition, we show that putative de novo proteins have an excess of substitutions between charged amino acids compared with the neutral expectation, which is reflected in the rapid loss of their initial highly basic character. The study supports high evolutionary dynamics of different kinds of new genes at the species level, in sharp contrast with the stability observed at later stages., We acknowledge funding from Ministerio de Ciencia e Innovación Agencia Estatal de Investigación grant PGC2018-094091-B-I00 (cofunded by Fondo Europeo de Desarrollo Regional), as well as grants PID2021-122726NB-I00 and PID2021-122830OB-C43 funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”, by the “European Union”. We also acknowledge funding from Generalitat de Catalunya, grant 2021SGR00042. The work was also funded by the European Union (ERC, NovoGenePop, project number 101052538). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

IntSat: integer linear programming by conflict-driven constraint learning

  • Nieuwenhuis, Robert Lukas Mario
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
State-of-the-art SAT solvers are nowadays able to handle huge real-world instances. The key to this success is the Conflict-Driven Clause-Learning (CDCL) scheme, which encompasses a number of techniques that exploit the conflicts that are encountered during the search for a solution. In this article, we extend these techniques to Integer Linear Programming (ILP), where variables may take general integer values instead of purely binary ones, constraints are more expressive than just propositional clauses, and there may be an objective function to optimize. We explain how these methods can be implemented efficiently and discuss possible improvements. Our work is backed with a basic implementation showing that, even in this far less mature stage, our techniques are already a useful complement to the state of the art in ILP., All authors are supported by grant PID2021-122830OB-C43, funded by MCIN/ AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Using execution logs for improving pseudo-Boolean propagation

  • Nieuwenhuis, Robert Lukas Mario
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
  • Zhao, Rui
Among all procedures that CDCL-based SAT solvers implement, unit propagation dominates the total running time. Hence, it is not a surprise that large research efforts have been invested on improving it. As a result, the two-watched-literal scheme, enhanced with implementation details boosting its performance, emerged as the dominant method. The importance of unit propagation in pseudo-Boolean solvers is similar. However, no dominant method exists: counter and watch-based propagation are well-suited for different types of constraints, opening the door to hybrid methods. The higher complexity of implementing pseudo-Boolean solvers has shifted the research focus to higher-level aspects of other procedures, considering implementation details of unit propagation not a priority. In this paper, we first present execution logs: a novel methodology that allows us to precisely evaluate the performance of different propagation procedures. Secondly, we show how both counter and watch-based propagation routines in the RoundingSat solver can be largely improved thanks to a careful analysis of various implementation issues. Thirdly, a detailed analysis shows that hybrid methods outperform the ones based on a single technique. Finally, our experiments reveal that improvements in propagation lead to a clearly better overall performance of the solver., All authors are supported by grant PID2021-122830OB-C43, funded by project MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”, and by grant PID2024-157044OB-C32, funded by MICIU /AEI /10.13039/501100011033 / FEDER, UE. Second and third authors are supported by Barcelogic through research grants C-11423 and C-11422, respectively., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Unique features of satellite DNA transcription in different tissues of Caenorhabditis elegans

  • Subirana Torrent, Juan A.
  • Messeguer Peypoch, Xavier
A large part of the genome is known to be transcribed as non-coding DNA including some tandem repeats (satellites) such as telomeric/centromeric satellites in different species. However, there has been no detailed study on the eventual transcription of the interspersed satellites found in many species. In the present paper, we studied the transcription of the abundant DNA satellites in the nematode Caenorhabditis elegans using available RNA-Seq results. We found that many of them have been transcribed, but usually in an irregular manner; different regions of a satellite have been transcribed with variable efficiency. Satellites with a similar repeat sequence also have a different transcription pattern depending on their position in the genome. We also describe the peculiar features of satellites associated with Helitron transposons in C. elegans. Our demonstration that some satellite RNAs are transcribed adds a new family of non-coding RNAs, a new element in the world of RNA interference, with new paths for the control of mRNA translation. This is a field that requires further investigation and will provide a deeper understanding of gene expression and control., This work was supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On learning when to decompose graphical models

  • Petrova, Aleksandra
  • Larrosa Bondia, Francisco Javier
Decomposition is a well-known algorithmic technique for Graphical Models. It is commonly believed that such a technique is cost-effective for instances with low width. In this paper, we show on a large data set of real-life inspired instances that this is not the case. To better understand this result, we narrow our study and consider k-tree instances where the width is well controlled and get similar results. Finally, we show that by adding a few simple features and using simple Machine Learning models we can predict the convenience to decompose with an accuracy of more than 85%, which produces time reductions in standard benchmarks of nearly 90%., Supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”., Peer Reviewed, Postprint (author's final draft)