Pasar al contenido principal

RAZONAMIENTO FORMAL PARA TECNOLOGIAS FACILITADORAS Y EMERGENTES

RTI2018-094403-B-C33

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2018
Plan Estatal 2017-2020 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): 22
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Unique features of tandem repeats in bacteria

  • Subirana Torrent, Juan A.|||0000-0002-1706-9341
  • Messeguer Peypoch, Xavier|||0000-0001-7430-4857
DNA tandem repeats, or satellites, are well described in eukaryotic species, but little is known about their prevalence across prokaryotes. Here, we performed the most complete characterization to date of satellites in bacteria. We identified 121,638 satellites from 12,233 fully sequenced and assembled bacterial genomes with a very uneven distribution. We also determined the families of satellites which have a related sequence. There are 85 genomes that are particularly satellite rich and contain several families of satellites of yet unknown function. Interestingly, we only found two main types of noncoding satellites, depending on their repeat sizes, 22/44 or 52¿nucleotides (nt). An intriguing feature is the constant size of the repeats in the genomes of different species, whereas their sequences show no conservation. Individual species also have several families of satellites with the same repeat length and different sequences. This result is in marked contrast with previous findings in eukaryotes, where noncoding satellites of many sizes are found in any species investigated. We describe in greater detail these noncoding satellites in the spirochete Leptospira interrogans and in several bacilli. These satellites undoubtedly play a specific role in the species which have acquired them. We discuss the possibility that they represent binding sites for transcription factors not previously described or that they are involved in the stabilization of the nucleoid through interaction with proteins. IMPORTANCE We found an enigmatic group of noncoding satellites in 85 bacterial genomes with a constant repeat size but variable sequence. This pattern of DNA organization is unique and had not been previously described in bacteria. These findings strongly suggest that satellite size in some bacteria is under strong selective constraints and thus that satellites are very likely to play a fundamental role. We also provide a list and properties of all satellites in 12,233 genomes, which may be used for further genomic analysis., This work was supported by Ministerio de Ciencia e Innovación–Agencia Estatal de Investigación, Spain (projects TIN2015-69175-C4-3-R and RTI2018-094403-B-C33), and FEDER., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Uncovering de novo gene birth in yeast using deep transcriptomics

  • Blevins, William R.
  • Ruiz Orera, Jorge
  • Messeguer Peypoch, Xavier|||0000-0001-7430-4857
  • Blasco Moreno, Bernat
  • Villanueva Cañas, José Luis
  • Espinar Calvo, Lorena
  • Díez Antón, Juana
  • Carey, Lucas B.
  • Albà Soler, M. Mar
De novo gene origination has been recently established as an important mechanism for the formation of new genes. In organisms with a large genome, intergenic and intronic regions provide plenty of raw material for new transcriptional events to occur, but little is know about how de novo transcripts originate in more densely-packed genomes. Here, we identify 213 de novo originated transcripts in Saccharomyces cerevisiae using deep transcriptomics and genomic synteny information from multiple yeast species grown in two different conditions. We find that about half of the de novo transcripts are expressed from regions which already harbor other genes in the opposite orientation; these transcripts show similar expression changes in response to stress as their overlapping counterparts, and some appear to translate small proteins. Thus, a large fraction of de novo genes in yeast are likely to co-evolve with already existing genes., The work was funded by grants PGC2018-094091-B-I00, BFU2015-65235-P, BFU2015-68351-P, BFU2016-80039-R, TIN2015-69175-C4-3-R and RTI2018-094403-B-C33 from Spanish Government—FEDER (EU), and from grant PT17/0009/0014 from Instituto de Salud Carlos III—FEDER. We also received funding from the “Maria de Maeztu” Programme for Units of Excellence in R&D (MDM-2014-0370) and from Agència de Gestió d’Ajuts Universitaris i de Recerca Generalitat de Catalunya (AGAUR), grants number 2014SGR1121, 2014SGR0974, 2017SGR1054 and 2017SGR01020 and, predoctoral fellowship (FI) to W.R.B., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Proof complexity for the maximum satisfiability problem and its use in SAT refutations

  • Rollón Rico, Emma|||0000-0001-8021-9464
  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
MaxSAT, the optimization version of the well-known SAT problem, has attracted a lot of research interest in the past decade. Motivated by the many important applications and inspired by the success of modern SAT solvers, researchers have developed many MaxSAT solvers. Since most research is algorithmic, its significance is mostly evaluated empirically. In this paper, we want to address MaxSAT from the more formal point of view of proof complexity. With that aim, we start providing basic definitions and proving some basic results. Then we analyse the effect of adding split and virtual, two original inference rules, to MaxSAT resolution. We show that each addition makes the resulting proof system stronger, even when virtual is restricted to empty clauses (0-virtual). We also analyse the power of our proof systems in the particular case of SAT refutations. We show that our strongest system, ResSV, is equivalent to circular and dual rail with split. We also analyse empirically some known gadget-based reformulations. Our results seem to indicate that the advantage of these three seemingly different systems over general resolution comes mainly from their ability of augmenting the original formula with hypothetical inconsistencies, as captured in a very simple way by the virtual rule., Under project RTI2018-094403-B-C33 funded by MCIN/AEI/ 10.13039/501100011033 and FEDER ”Una manera de hacer Europa", Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Tandem repeats in Bacillus: Unique features and taxonomic distribution

  • Subirana Torrent, Juan A.|||0000-0002-1706-9341
  • Messeguer Peypoch, Xavier|||0000-0001-7430-4857
Little is known about DNA tandem repeats across prokaryotes. We have recently described an enigmatic group of tandem repeats in bacterial genomes with a constant repeat size but variable sequence. These findings strongly suggest that tandem repeat size in some bacteria is under strong selective constraints. Here, we extend these studies and describe tandem repeats in a large set of Bacillus. Some species have very few repeats, while other species have a large number. Most tandem repeats have repeats with a constant size (either 52 or 20–21 nt), but a variable sequence. We characterize in detail these intriguing tandem repeats. Individual species have several families of tandem repeats with the same repeat length and different sequence. This result is in strong contrast with eukaryotes, where tandem repeats of many sizes are found in any species. We discuss the possibility that they are transcribed as small RNA molecules. They may also be involved in the stabilization of the nucleoid through interaction with proteins. We also show that the distribution of tandem repeats in different species has a taxonomic significance. The data we present for all tandem repeats and their families in these bacterial species will be useful for further genomic studies., This work was supported by Ministerio de Ciencia e Innovación –Agencia Estatal de Investigación, Spain (Project RTI2018-094403-B-C33) and FEDER., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Choosing the root of the tree decomposition when solving WCSPs: preliminary results

  • Petrova, Aleksandra
  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
  • Rollón Rico, Emma|||0000-0001-8021-9464
In this paper we analyze the effect of selecting the root in a tree decomposition when using decomposition-based backtracking algorithms. We focus on optimization tasks for Graphical Models using the BTD algorithm. We show that the choice of the root typically has a dramatic effect in the solving performance. Then we investigate different simple measures to predict near optimal roots. Our study shows that correlations are often low, so the automatic selection of a near optimal root will require more sophisticated techniques., Projects RTI2018-094403-B-C33, funded by: FEDER/Ministerio de Ciencia e Innovación Agencia Estatal de Investigación,Spain, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Employee scheduling with SAT-based pseudo-boolean constraint solving

  • Nieuwenhuis, Robert Lukas Mario|||0000-0002-6489-2138
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
  • Rollón Rico, Emma|||0000-0001-8021-9464
The aim of this paper is practical: to show that, for at least one important real-world problem, modern SAT-based technology can beat the extremely mature branch-and-cut solving methods implemented in well-known state-of-the-art commercial solvers such as CPLEX or Gurobi. The problem of employee scheduling consists in assigning a work schedule to each of the employees of an organization, in such a way that demands are met, legal and contractual constraints are respected, and staff preferences are taken into account. This problem is typically handled by first modeling it as a 0-1 integer linear program (ILP). Our experimental setup considers as a case study the 0-1 ILPs obtained from the staff scheduling of a real-world car rental company, and carefully compares the performance of CPLEX and Gurobi with our own simple conflict-driven constraint-learning pseudo-Boolean solver., Project RTI2018-094403-B-C33 funded by MCIN (Ministerio de Ciencia e Innovación)/AEI/10.13039/501100011033/FEDER ‘‘Una manera de hacer Europa.’’, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Decision levels are stable: towards better SAT heuristics

  • Nieuwenhuis, Robert Lukas Mario|||0000-0002-6489-2138
  • Lozano Navarro, Adrián
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
We shed new light on the Literal Block Distance (LBD) and glue-based heuristics used in current SAT solvers. For this, we first introduce the concept of stickiness: given a run of a CDCL SAT solver, for each pair of literals we define, by a real value between 0 and 1, how sticky they are, basically, how frequently they are set at the same decision level. By means of a careful and detailed experimental setup and analysis, we confirm the following quite surprising fact: given a SAT instance, when running different CDCL SAT solvers on it, no matter their settings or random seeds, the stickiness relation between literals is always very similar, in a precisely defined sense. We analyze how quickly stickiness stabilizes in a run (quite quickly), and show that it is stable even under different encodings of cardinality constraints. We then describe how and why these solid new insights lead to heuristics refinements for SAT (and extensions, such as SMT) and improved information sharing in parallel solvers., Projects TIN2015-69175-C4-3-R (funded by FEDER/MINECO) and RTI2018-094403-B-C33 (funded by FEDER/Ministerio de Ciencia e Innovacion, Agencia Estatal de Investigacion, Spain), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Incomplete SMT techniques for solving non-linear formulas over the integers

  • Borralleras Andreu, Cristina
  • Larraz Hurtado, Daniel|||0000-0001-5305-7340
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rubio Gimeno, Alberto|||0000-0002-0501-9830
We present new methods for solving the Satisfiability Modulo Theories problem over the theory of QuantifierFree Non-linear Integer Arithmetic, SMT(QF-NIA), which consists of deciding the satisfiability of ground formulas with integer polynomial constraints. Following previous work, we propose to solve SMT(QF-NIA) instances by reducing them to linear arithmetic: non-linear monomials are linearized by abstracting them with fresh variables and by performing case splitting on integer variables with finite domain. For variables that do not have a finite domain, we can artificially introduce one by imposing a lower and an upper bound and iteratively enlarge it until a solution is found (or the procedure times out). The key for the success of the approach is to determine, at each iteration, which domains have to be enlarged. Previously, unsatisfiable cores were used to identify the domains to be changed, but no clue was obtained as to how large the new domains should be. Here, we explain two novel ways to guide this process by analyzing solutions to optimization problems: (i) to minimize the number of violated artificial domain bounds, solved via a Max-SMT solver, and (ii) to minimize the distance with respect to the artificial domains, solved via an Optimization Modulo Theories (OMT) solver. Using this SMT-based optimization technology allows smoothly extending the method to also solve Max-SMT problems over non-linear integer arithmetic. Finally, we leverage the resulting Max-SMT(QF-NIA) techniques to solve ∃∀ formulas in a fragment of quantified non-linear arithmetic that appears commonly in verification and synthesis applications., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Augmenting the power of (partial) MaxSat resolution with extension

  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
  • Rollón Rico, Emma|||0000-0001-8021-9464
The refutation power of SAT and MaxSAT resolution is challenged by problems like the soft and hard Pigeon Hole Problem PHP for which short refutations do not exist. In this paper we augment the MaxSAT resolution proof system with an extension rule. The new proof system MaxResE is sound and complete, and more powerful than plain MaxSAT resolution, since it can refute the soft and hard PHP in polynomial time. We show that MaxResE refutations actually subtract lower bounds from the objective function encoded by the formulas. The resulting formula is the residual after the lower bound extraction. We experimentally show that the residual of the soft PHP (once its necessary cost of 1 has been efficiently subtracted with MaxResE) is a concise, easy to solve, satisfiable problem., This work was funded partially by the Spanish MINECO and MICINN projects TIN2015-69175-C4-3-R and RTI2018-094403-B-C33., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Dna satellites are transcribed as part of the non-coding genome in eukaryotes and bacteria

  • Subirana Torrent, Juan A.|||0000-0002-1706-9341
  • Messeguer Peypoch, Xavier|||0000-0001-7430-4857
It has been shown in recent years that many repeated sequences in the genome are expressed as RNA transcripts, although the role of such RNAs is poorly understood. Some isolated and tandem repeats (satellites) have been found to be transcribed, such as mammalian Alu sequences and telomeric/centromeric satellites in different species. However, there is no detailed study on the eventual transcription of the interspersed satellites found in many species. Therefore, we decided to study for the first time the transcription of the abundant DNA satellites in the bacterium Bacillus coagulans and in the nematode Caenorhabditis elegans. We have updated the data for C. elegans satellites using the latest version of the genome. We analyzed the transcription of satellites in both species in available RNA-seq results and found that they are widely transcribed. Our demonstration that satellite RNAs are transcribed adds a new family of non-coding RNAs. This is a field that requires further investigation and will provide a deeper understanding of gene expression and control., This work was supported by Ministerio de Ciencia e Innovación, Spain [Project RTI2018-094403-B-C33 funded by MCIN/ AEI 10.13039/501100011033/ FEDER]., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A heuristic approach to the design of optimal cross-docking boxes

  • Nieuwenhuis, Robert Lukas Mario|||0000-0002-6489-2138
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
Multinational companies frequently work with manufacturers that receive large orders for different products (or product varieties: size, shape, color, texture, material), to serve thousands of different final destinations (e.g., shops) requesting a combination of different quantities of each product. It is not the manufacturers’ task to create the individual shipments for each final destination. But manufacturers can deliver part of their production in so-called cross-docking boxes (or other containers) of a few+ (say, three) types, each type containing a given assortment, i.e., different quantities of different products. At a logistics center, the shipments for each destination are then made of cross-docking boxes plus additional “picking” units. The expensive part is the picking, since cross-docking boxes require little or no manipulation. The problem we solve in this paper is, given a large set of orders for each destination, to design the cross-docking box types in order to minimize picking. We formally define a variant of this problem and develop a heuristic method to solve it. Finally, we present extensive experimental results on a large set of real-world benchmarks proving that our approach gives high-quality solutions (optimal or near optimal) in a very limited amount of time., This work was supported in part by the Spanish Ministerio de Ciencia e Innovación (MICINN) Project under Grant RTI2018-094403-B-C33., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Employee scheduling with SAT-based pseudo-boolean constraint solving

  • Nieuwenhuis, Robert Lukas Mario
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
  • Rollón Rico, Emma
The aim of this paper is practical: to show that, for at least one important real-world problem, modern SAT-based technology can beat the extremely mature branch-and-cut solving methods implemented in well-known state-of-the-art commercial solvers such as CPLEX or Gurobi. The problem of employee scheduling consists in assigning a work schedule to each of the employees of an organization, in such a way that demands are met, legal and contractual constraints are respected, and staff preferences are taken into account. This problem is typically handled by first modeling it as a 0-1 integer linear program (ILP). Our experimental setup considers as a case study the 0-1 ILPs obtained from the staff scheduling of a real-world car rental company, and carefully compares the performance of CPLEX and Gurobi with our own simple conflict-driven constraint-learning pseudo-Boolean solver., Project RTI2018-094403-B-C33 funded by MCIN (Ministerio de Ciencia e Innovación)/AEI/10.13039/501100011033/FEDER ‘‘Una manera de hacer Europa.’’, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Choosing the root of the tree decomposition when solving WCSPs: preliminary results

  • Petrova, Aleksandra
  • Larrosa Bondia, Francisco Javier
  • Rollón Rico, Emma
In this paper we analyze the effect of selecting the root in a tree decomposition when using decomposition-based backtracking algorithms. We focus on optimization tasks for Graphical Models using the BTD algorithm. We show that the choice of the root typically has a dramatic effect in the solving performance. Then we investigate different simple measures to predict near optimal roots. Our study shows that correlations are often low, so the automatic selection of a near optimal root will require more sophisticated techniques., Projects RTI2018-094403-B-C33, funded by: FEDER/Ministerio de Ciencia e Innovación Agencia Estatal de Investigación,Spain, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Augmenting the power of (partial) MaxSat resolution with extension

  • Larrosa Bondia, Francisco Javier
  • Rollón Rico, Emma
The refutation power of SAT and MaxSAT resolution is challenged by problems like the soft and hard Pigeon Hole Problem PHP for which short refutations do not exist. In this paper we augment the MaxSAT resolution proof system with an extension rule. The new proof system MaxResE is sound and complete, and more powerful than plain MaxSAT resolution, since it can refute the soft and hard PHP in polynomial time. We show that MaxResE refutations actually subtract lower bounds from the objective function encoded by the formulas. The resulting formula is the residual after the lower bound extraction. We experimentally show that the residual of the soft PHP (once its necessary cost of 1 has been efficiently subtracted with MaxResE) is a concise, easy to solve, satisfiable problem., This work was funded partially by the Spanish MINECO and MICINN projects TIN2015-69175-C4-3-R and RTI2018-094403-B-C33., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Dna satellites are transcribed as part of the non-coding genome in eukaryotes and bacteria

  • Subirana Torrent, Juan A.
  • Messeguer Peypoch, Xavier
It has been shown in recent years that many repeated sequences in the genome are expressed as RNA transcripts, although the role of such RNAs is poorly understood. Some isolated and tandem repeats (satellites) have been found to be transcribed, such as mammalian Alu sequences and telomeric/centromeric satellites in different species. However, there is no detailed study on the eventual transcription of the interspersed satellites found in many species. Therefore, we decided to study for the first time the transcription of the abundant DNA satellites in the bacterium Bacillus coagulans and in the nematode Caenorhabditis elegans. We have updated the data for C. elegans satellites using the latest version of the genome. We analyzed the transcription of satellites in both species in available RNA-seq results and found that they are widely transcribed. Our demonstration that satellite RNAs are transcribed adds a new family of non-coding RNAs. This is a field that requires further investigation and will provide a deeper understanding of gene expression and control., This work was supported by Ministerio de Ciencia e Innovación, Spain [Project RTI2018-094403-B-C33 funded by MCIN/ AEI 10.13039/501100011033/ FEDER]., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Incomplete SMT techniques for solving non-linear formulas over the integers

  • Borralleras Andreu, Cristina
  • Larraz Hurtado, Daniel
  • Rodríguez Carbonell, Enric
  • Oliveras Llunell, Albert
  • Rubio Gimeno, Alberto
We present new methods for solving the Satisfiability Modulo Theories problem over the theory of QuantifierFree Non-linear Integer Arithmetic, SMT(QF-NIA), which consists of deciding the satisfiability of ground formulas with integer polynomial constraints. Following previous work, we propose to solve SMT(QF-NIA) instances by reducing them to linear arithmetic: non-linear monomials are linearized by abstracting them with fresh variables and by performing case splitting on integer variables with finite domain. For variables that do not have a finite domain, we can artificially introduce one by imposing a lower and an upper bound and iteratively enlarge it until a solution is found (or the procedure times out). The key for the success of the approach is to determine, at each iteration, which domains have to be enlarged. Previously, unsatisfiable cores were used to identify the domains to be changed, but no clue was obtained as to how large the new domains should be. Here, we explain two novel ways to guide this process by analyzing solutions to optimization problems: (i) to minimize the number of violated artificial domain bounds, solved via a Max-SMT solver, and (ii) to minimize the distance with respect to the artificial domains, solved via an Optimization Modulo Theories (OMT) solver. Using this SMT-based optimization technology allows smoothly extending the method to also solve Max-SMT problems over non-linear integer arithmetic. Finally, we leverage the resulting Max-SMT(QF-NIA) techniques to solve ∃∀ formulas in a fragment of quantified non-linear arithmetic that appears commonly in verification and synthesis applications., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Proof complexity for the maximum satisfiability problem and its use in SAT refutations

  • Rollón Rico, Emma
  • Larrosa Bondia, Francisco Javier
MaxSAT, the optimization version of the well-known SAT problem, has attracted a lot of research interest in the past decade. Motivated by the many important applications and inspired by the success of modern SAT solvers, researchers have developed many MaxSAT solvers. Since most research is algorithmic, its significance is mostly evaluated empirically. In this paper, we want to address MaxSAT from the more formal point of view of proof complexity. With that aim, we start providing basic definitions and proving some basic results. Then we analyse the effect of adding split and virtual, two original inference rules, to MaxSAT resolution. We show that each addition makes the resulting proof system stronger, even when virtual is restricted to empty clauses (0-virtual). We also analyse the power of our proof systems in the particular case of SAT refutations. We show that our strongest system, ResSV, is equivalent to circular and dual rail with split. We also analyse empirically some known gadget-based reformulations. Our results seem to indicate that the advantage of these three seemingly different systems over general resolution comes mainly from their ability of augmenting the original formula with hypothetical inconsistencies, as captured in a very simple way by the virtual rule., Under project RTI2018-094403-B-C33 funded by MCIN/AEI/ 10.13039/501100011033 and FEDER ”Una manera de hacer Europa", Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Tandem repeats in Bacillus: Unique features and taxonomic distribution

  • Subirana Torrent, Juan A.
  • Messeguer Peypoch, Xavier
Little is known about DNA tandem repeats across prokaryotes. We have recently described an enigmatic group of tandem repeats in bacterial genomes with a constant repeat size but variable sequence. These findings strongly suggest that tandem repeat size in some bacteria is under strong selective constraints. Here, we extend these studies and describe tandem repeats in a large set of Bacillus. Some species have very few repeats, while other species have a large number. Most tandem repeats have repeats with a constant size (either 52 or 20–21 nt), but a variable sequence. We characterize in detail these intriguing tandem repeats. Individual species have several families of tandem repeats with the same repeat length and different sequence. This result is in strong contrast with eukaryotes, where tandem repeats of many sizes are found in any species. We discuss the possibility that they are transcribed as small RNA molecules. They may also be involved in the stabilization of the nucleoid through interaction with proteins. We also show that the distribution of tandem repeats in different species has a taxonomic significance. The data we present for all tandem repeats and their families in these bacterial species will be useful for further genomic studies., This work was supported by Ministerio de Ciencia e Innovación –Agencia Estatal de Investigación, Spain (Project RTI2018-094403-B-C33) and FEDER., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Unique features of tandem repeats in bacteria

  • Subirana Torrent, Juan A.
  • Messeguer Peypoch, Xavier
DNA tandem repeats, or satellites, are well described in eukaryotic species, but little is known about their prevalence across prokaryotes. Here, we performed the most complete characterization to date of satellites in bacteria. We identified 121,638 satellites from 12,233 fully sequenced and assembled bacterial genomes with a very uneven distribution. We also determined the families of satellites which have a related sequence. There are 85 genomes that are particularly satellite rich and contain several families of satellites of yet unknown function. Interestingly, we only found two main types of noncoding satellites, depending on their repeat sizes, 22/44 or 52¿nucleotides (nt). An intriguing feature is the constant size of the repeats in the genomes of different species, whereas their sequences show no conservation. Individual species also have several families of satellites with the same repeat length and different sequences. This result is in marked contrast with previous findings in eukaryotes, where noncoding satellites of many sizes are found in any species investigated. We describe in greater detail these noncoding satellites in the spirochete Leptospira interrogans and in several bacilli. These satellites undoubtedly play a specific role in the species which have acquired them. We discuss the possibility that they represent binding sites for transcription factors not previously described or that they are involved in the stabilization of the nucleoid through interaction with proteins. IMPORTANCE We found an enigmatic group of noncoding satellites in 85 bacterial genomes with a constant repeat size but variable sequence. This pattern of DNA organization is unique and had not been previously described in bacteria. These findings strongly suggest that satellite size in some bacteria is under strong selective constraints and thus that satellites are very likely to play a fundamental role. We also provide a list and properties of all satellites in 12,233 genomes, which may be used for further genomic analysis., This work was supported by Ministerio de Ciencia e Innovación–Agencia Estatal de Investigación, Spain (projects TIN2015-69175-C4-3-R and RTI2018-094403-B-C33), and FEDER., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A heuristic approach to the design of optimal cross-docking boxes

  • Nieuwenhuis, Robert Lukas Mario
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
Multinational companies frequently work with manufacturers that receive large orders for different products (or product varieties: size, shape, color, texture, material), to serve thousands of different final destinations (e.g., shops) requesting a combination of different quantities of each product. It is not the manufacturers’ task to create the individual shipments for each final destination. But manufacturers can deliver part of their production in so-called cross-docking boxes (or other containers) of a few+ (say, three) types, each type containing a given assortment, i.e., different quantities of different products. At a logistics center, the shipments for each destination are then made of cross-docking boxes plus additional “picking” units. The expensive part is the picking, since cross-docking boxes require little or no manipulation. The problem we solve in this paper is, given a large set of orders for each destination, to design the cross-docking box types in order to minimize picking. We formally define a variant of this problem and develop a heuristic method to solve it. Finally, we present extensive experimental results on a large set of real-world benchmarks proving that our approach gives high-quality solutions (optimal or near optimal) in a very limited amount of time., This work was supported in part by the Spanish Ministerio de Ciencia e Innovación (MICINN) Project under Grant RTI2018-094403-B-C33., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Uncovering de novo gene birth in yeast using deep transcriptomics

  • Blevins, William R.
  • Ruiz Orera, Jorge
  • Messeguer Peypoch, Xavier
  • Blasco Moreno, Bernat
  • Villanueva Cañas, José Luis
  • Espinar Calvo, Lorena
  • Díez Antón, Juana
  • Carey, Lucas B.
  • Albà Soler, M. Mar
De novo gene origination has been recently established as an important mechanism for the formation of new genes. In organisms with a large genome, intergenic and intronic regions provide plenty of raw material for new transcriptional events to occur, but little is know about how de novo transcripts originate in more densely-packed genomes. Here, we identify 213 de novo originated transcripts in Saccharomyces cerevisiae using deep transcriptomics and genomic synteny information from multiple yeast species grown in two different conditions. We find that about half of the de novo transcripts are expressed from regions which already harbor other genes in the opposite orientation; these transcripts show similar expression changes in response to stress as their overlapping counterparts, and some appear to translate small proteins. Thus, a large fraction of de novo genes in yeast are likely to co-evolve with already existing genes., The work was funded by grants PGC2018-094091-B-I00, BFU2015-65235-P, BFU2015-68351-P, BFU2016-80039-R, TIN2015-69175-C4-3-R and RTI2018-094403-B-C33 from Spanish Government—FEDER (EU), and from grant PT17/0009/0014 from Instituto de Salud Carlos III—FEDER. We also received funding from the “Maria de Maeztu” Programme for Units of Excellence in R&D (MDM-2014-0370) and from Agència de Gestió d’Ajuts Universitaris i de Recerca Generalitat de Catalunya (AGAUR), grants number 2014SGR1121, 2014SGR0974, 2017SGR1054 and 2017SGR01020 and, predoctoral fellowship (FI) to W.R.B., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Decision levels are stable: towards better SAT heuristics

  • Nieuwenhuis, Robert Lukas Mario
  • Lozano Navarro, Adrián
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
We shed new light on the Literal Block Distance (LBD) and glue-based heuristics used in current SAT solvers. For this, we first introduce the concept of stickiness: given a run of a CDCL SAT solver, for each pair of literals we define, by a real value between 0 and 1, how sticky they are, basically, how frequently they are set at the same decision level. By means of a careful and detailed experimental setup and analysis, we confirm the following quite surprising fact: given a SAT instance, when running different CDCL SAT solvers on it, no matter their settings or random seeds, the stickiness relation between literals is always very similar, in a precisely defined sense. We analyze how quickly stickiness stabilizes in a run (quite quickly), and show that it is stable even under different encodings of cardinality constraints. We then describe how and why these solid new insights lead to heuristics refinements for SAT (and extensions, such as SMT) and improved information sharing in parallel solvers., Projects TIN2015-69175-C4-3-R (funded by FEDER/MINECO) and RTI2018-094403-B-C33 (funded by FEDER/Ministerio de Ciencia e Innovacion, Agencia Estatal de Investigacion, Spain), Peer Reviewed, Postprint (published version)