Ingeniería Informática y Ciencias de la Computación - Tesis Doctoradohttp://repositorio.udec.cl/jspui/handle/11594/2162024-03-29T03:24:44Z2024-03-29T03:24:44ZEfficient query processing for multigranular data.Gatica Romero, Diegohttp://repositorio.udec.cl/jspui/handle/11594/118972024-03-21T06:03:10Z2024-01-01T00:00:00ZEfficient query processing for multigranular data.
Gatica Romero, Diego
Spatial and temporal attributes are typical examples of data that can be represented at different levels of granularity or resolution. The massive amount of this type of data makes it impractical to store and process data without making use of efficient algorithms and structures. In search of a way to handle multigranular data, several data models have been proposed; however, there is no efficient implementation in terms of space usage and query time for any of the various existing models for handling multigranular data. In this thesis, we study algorithms and data structures to process different queries on multigranular models, specifically, the work done uses succinct data structures and achieves a good trade-off between space usage and query time.
In particular, we start by proposing a succinct data structure and algorithm for the implementation of a multigranular model that is general enough to be used in different domains. This model is based on the relations of subsumption and disjoint between its elements (i.e. granules), and their respective negations, and it proposes the strategy of deriving new relations, in order to reduce the space to be used. The proposed structure used (|E| − |V |) log2 |V | + O(|E|) space to store a graph with V vertices and E edges to store a graph that represent the subsumption relation, plus |Er| log |V|+|Er|+|V |+o(|Er| + |V |) for for each of the other relationships, and improves the derivation of new relations, compared to other implementations. A second succinct data structure is proposed, with a focus on the spatial domain by providing algorithms for processing topological queries like inclusion, disjointness, and adjacency between regions on a multi resolution context. In the case of a set of n regions without a hierarchy, we can manipulate it efficiently using 4n + o(n) bit, for the case when we have a hierarchy of height h, our structure proposed requires as little as O(n log h) bits, while maintaining a similar query time compared to a non-compact implementation.
Tesis para optar al grado de Doctorado en Ciencias de la Computación
2024-01-01T00:00:00ZStudy of the block-sequential operator on Boolean networks. Application to discrete network analysis.Cabrera Crot, Luis Emiliohttp://repositorio.udec.cl/jspui/handle/11594/118152024-01-27T06:02:40Z2024-01-01T00:00:00ZStudy of the block-sequential operator on Boolean networks. Application to discrete network analysis.
Cabrera Crot, Luis Emilio
A Boolean network is a system of n interacting Boolean variables, which evolve, in a discrete time, according to a regulation rule and to a predefined updating scheme. They have applications in many areas, including circuit theory, computer science, social networks and biological systems.
The structure of such a network is often represented by a digraph, called interaction digraph,
where vertices are network components, and where there is an arc from one component to another when the evolution of the latter depends on the evolution of the former. The relationship between the structure of a regulatory network and its dynamical behavior is crucial to understand for instance how and why biological networks have evolved. Further, this relationship can be used to construct networks with desirable dynamical properties. In the original scheme of a Boolean network all the nodes are synchronously updated at each time step (this scheme is also called parallel schedule). A more general scheme, introduced in [67], is to consider that the set of network nodes is partitioned into blocks and that the nodes in a block are updated simultaneously. Differences in the dynamical behaviors of Boolean networks with different update schedules has been studied mainly from an experimental and statistical point of view. In this tesis, the variations of the interaction digraph of a Boolean network with respect to changes in the update schedule and its relation with some dynamical properties of the network are studied. In order to achieve this goal, three main topics are discussed. First, the variations in the parallel digraph of some structural characteristics (number of strongly connect components, transversal number, packing number) with respect to changes in the update schedule are analyzed. Second, an algorithm is constructed to find the fixed points of a Boolean network taking advantage of knowledge about the upper bound of the fixed points of a network, in this case we use the positive transversal number. Finally, a new, so far unexplored problem is defined, which states that given a Boolean network f, find a Boolean network h and an update schedule s that are dynamically equivalent to f. In this sense, several variations of the original problem are presented, many of which can be solved in polynomial time.
Tesis para optar al grado de Doctor en Ciencias de la Computación.
2024-01-01T00:00:00ZMachine learning classification of single cell rna-seq across different types of cáncer.Vidal Miranda, Mabel Angélicahttp://repositorio.udec.cl/jspui/handle/11594/99442023-11-11T00:11:34Z2022-01-01T00:00:00ZMachine learning classification of single cell rna-seq across different types of cáncer.
Vidal Miranda, Mabel Angélica
Human cancers are complex ecosystems composed of different types of cells. The diverse
populations of co-existing cells within the same tumor that have genetic, functional, and
environmental differences determine the tumor heterogeneity, which is one of the major
challenges facing cancer diagnosis and treatment. The aim of this thesis was to apply
different machine learning methods to classify single cell RNA-seq (scRNA-seq) samples
across nine different types of cancer. We observed that T cells are the most abundant
datasets in public repositories due to their important role in immunotherapies. For this
reason, we performed an in-silico analysis from scRNA-seq data available in the Gene
Expression Omnibus. A őrst approach was to analyze and characterize genetic T cell
signatures from őve different types of cancer and apply dimensionality reduction and clus tering methods to identify subpopulations from malignant and non-malignant datasets.
This analysis revealed that pathways related to immune response, metabolism and viral
immunoregulation were observed exclusively in samples of malignant origin. A second
approach was to perform two deep learning models to classify cells from nine different
types of cancer, where the cells were grouped in the diversity of the cell state, giving
us a new perspective in the different classes of tumors present in our dataset. Finally,
we observed that working with unsupervised methods, our data help us understand the
heterogeneity between tumors. Characterization of cellular diversity was associated with
pathways that play a key role in tumor proliferation, progression, and regulation of the
microenvironmental immune response.
Tesis para optar al grado de Doctor en Ciencias de la Computación.
2022-01-01T00:00:00ZMutation testing techniques for mobile applications.Rodríguez Trujillo, Isyed de la Caridadhttp://repositorio.udec.cl/jspui/handle/11594/91672023-11-10T22:51:27Z2021-01-01T00:00:00ZMutation testing techniques for mobile applications.
Rodríguez Trujillo, Isyed de la Caridad
As it is well known, exhaustive testing of software systems (i.e.,
testing the system with its possible inputs and environmental conditions) is,
in practice, impossible, since it is unfeasible to reproduce all the running
situations. So, the tester must make decisions about which parts of the system
must be tested and the degree of depth of the test cases.
When a test engineer is testing a software artifact, he/she needs to
know which portions of the system are running their test cases. For this,
coverage criteria are used because they allow to know the "amount of
product" that is being tested (number of lines of code, methods, decisions,
conditions, etc.). If the tester knows the coverage that a set of test cases
reaches on the SUT (the System Under Test), he/she will be able to determine
which portions of the system are not being covered by the test cases:
• If the coverage is lower than a prefixed threshold, the tester must add
more test cases to cover the SUT more in depth, to force the execution
of the unexplored system areas.
Tesis para optar por el grado académico de Doctor en Ciencias de la Computación.
2021-01-01T00:00:00Z