Search

The mutational heterogeneity of tumours can be described with a tree representing the evolutionary history of the tumour. With noisy sequencing data there may be uncertainty in the inferred tree structure, while we may also wish to study patterns in the evolution of cancers in different patients. In such situations, understanding tree similarities is a key challenge, and therefore we present an approach to determine distances between trees. Considering the bounded height of trees, we determine the distances associated with the swap operations over strings. While in general, by solving the {\sc Maximum Common Almost $v$-tree} problem between two trees, we describe an efficient approach to determine the minimum number of operations to transform one tree into another. The inherent noise in current statistical methods for constructing mutation evolution trees of cancer cells presents a significant challenge: handling such collections of trees to determine a consensus tree that accurately represents the set and evaluating the extent of their variability or dispersion. Given a set of mutation trees and the notion of distance, there are at least two natural ways to define the ``target'' tree, such as a min-sum (\emph{median tree}) or a min-max (\emph{closest tree}) of a set of trees. Thus, considering a set of trees as input and dealing with the {\sc median} and {\sc closest} problems, we prove that both problems are \NP-complete, even with only three input trees. In addition, we develop algorithms to obtain upper bounds on the median and closest solutions, which are analysed by the experiments presented on generated and on real databases. We show a fast way to find consensus trees with better results than any tree in the input set while still preserving all internal structure.

Given a binary string $\omega$ over the alphabet $\{0, 1\}$, a vector $(a, b)$ is a Parikh vector if and only if a factor of $\omega$ contains exactly $a$ occurrences of $0$ and $b$ occurrences of $1$. Answering whether a vector is a Parikh vector of $\omega$ is known as the Binary Jumbled Indexing Problem (BJPMP) or the Histogram Indexing Problem. Most solutions to this problem rely on an $O(n)$ word-space index to answer queries in constant time, encoding the Parikh set of $\omega$, i.e., all its Parikh vectors. Cunha et al. (Combinatorial Pattern Matching, 2017) introduced an algorithm (JBM2017), which computes the index table in $O(n+\rho^2)$ time, where $\rho$ is the number of runs of identical digits in $\omega$, leading to $O(n^2)$ in the worst case. We prove that the average number of runs $\rho$ is $n/4$, confirming the quadratic behavior also in the average-case. We propose a new algorithm, SFTree, which uses a suffix tree to remove duplicate substrings. Although SFTree also has an average-case complexity of $\Theta(n^2)$ due to the fundamental reliance on run boundaries, it achieves practical improvements by minimizing memory access overhead through vectorization. The suffix tree further allows distinct substrings to be processed efficiently, reducing the effective cost of memory access. As a result, while both algorithms exhibit similar theoretical growth, SFTree significantly outperforms others in practice. Our analysis highlights both the theoretical and practical benefits of the SFTree approach, with potential extensions to other applications of suffix trees., Comment: An extended abstract of this work was presented in COCOON 2024

Genome rearrangement has been an active area of research in computational comparative genomics for the last three decades. While initially mostly an interesting algorithmic endeavor, now the practical application by applying rearrangement distance methods and more advanced phylogenetic tasks is becoming common practice, given the availability of many completely sequenced genomes. Several genome rearrangement models have been developed over time, sometimes with surprising computational properties. A prominent example is the fact that computing the reversal distance of two signed permutations is possible in linear time, while for two unsigned permutations it is NP-hard. Therefore one has always to be careful about the precise problem formulation and complexity analysis of rearrangement problems in order not to be fooled. The double distance is the minimum number of genomic rearrangements between a singular and a duplicated genome that, in addition to rearrangements, are separated by a whole genome duplication. At the same time it allows to assign the genes of the duplicated genome to the two paralogous chromosome copies that existed right after the duplication event. Computing the double distance is another example of a tricky hardness landscape: If the distance measure underlying the double distance is the simple breakpoint distance, the problem can be solved in linear time, while with the more elaborate DCJ distance it is NP-hard. Indeed, there is a family of distance measures, parameterized by an even number k, between the breakpoint distance (k=2) and the DCJ distance (k=\infty). Little was known about the hardness border between these extremes; the problem complexity was known only for k=4 and k=6. In this paper, we close the gap, providing a full picture of the hardness landscape when computing the double distance.

The automotive industry is experiencing a massive paradigm shift. Cars are becoming increasingly autonomous, connected, and computerized. Modern electrical/electronic (E/E) architectures are pushing for an unforeseen functionality integration density, resulting in physically separate Electronic Control Units (ECUs) becoming virtualized and mapped to logical partitions within a single physical microcontroller (MCU). While functional safety (FuSa) has been pivotal for vehicle certification for decades, the increasing connectivity and advances have opened the door for a number of car hacks and attacks. This development drives (cyber-)security requirements in cars, and has paved the way for the release of the new security certification standard ISO21434. RISC-V has great potential to transform automotive computing systems, but we argue that current ISA/extensions are not ready yet. This paper provides our critical perspective on the existing RISC-V limitations, particularly on the upcoming WorldGuard technology, to address virtualized MCU requirements in line with foreseen automotive applications and ISO21434 directives. We then present our proposal for the required ISA extensions to address such limitations, mainly targeting initiator-side protection. Finally, we explain our roadmap towards a full open-source proof-of-concept (PoC), which includes extending QEMU, an open-source RISC-V core, and building a complete software stack.

Genome rearrangements are events in which large blocks of DNA exchange pieces during evolution. The analysis of such events is a tool for understanding evolutionary genomics, based on finding the minimum number of rearrangements to transform one genome into another. In a general scenario, more than two genomes are considered and we have new challenges. The {\sc Median} problem consists in finding, given three permutations and a distance metric, a permutation $s$ that minimizes the sum of the distances between $s$ and each input. We study the {\sc median} problem over \emph{swap} distances in permutations, for which the computational complexity has been open for almost 20 years (Eriksen, \emph{Theor. Compt. Sci.}, 2007). We consider this problem through some branches. We associate median solutions and interval convex sets, where the concept of graph convexity inspires the following investigation: Does a median permutation belong to every shortest path between one of the pairs of input permutations? We are able to partially answer this question, and as a by-product we solve a long open problem by proving that the {\sc Swap Median} problem is NP-hard. Furthermore, using a similar approach, we show that the {\sc Closest} problem, which seeks to minimize the maximum distance between the solution and the input permutations, is NP-hard even considering three input permutations. This gives a sharp dichotomy into the P vs. NP-hard approaches, since considering two input permutations the problem is easily solvable and considering any number of input permutations it is known to be NP-hard since 2007 (Popov, \emph{Theor. Compt. Sci.}, 2007). In addition, we show that {\sc Swap Median} and {\sc Swap Closest} are APX-hard problems.

Event extraction is an Information Retrieval task that commonly consists of identifying the central word for the event (trigger) and the event's arguments. This task has been extensively studied for English but lags behind for Portuguese, partly due to the lack of task-specific annotated corpora. This paper proposes a framework in which two separated BERT-based models were fine-tuned to identify and classify events in Portuguese documents. We decompose this task into two sub-tasks. Firstly, we use a token classification model to detect event triggers. To extract event arguments, we train a Question Answering model that queries the triggers about their corresponding event argument roles. Given the lack of event annotated corpora in Portuguese, we translated the original version of the ACE-2005 dataset (a reference in the field) into Portuguese, producing a new corpus for Portuguese event extraction. To accomplish this, we developed an automatic translation pipeline. Our framework obtains F1 marks of 64.4 for trigger classification and 46.7 for argument classification setting, thus a new state-of-the-art reference for these tasks in Portuguese.

Event extraction is an NLP task that commonly involves identifying the central word (trigger) for an event and its associated arguments in text. ACE-2005 is widely recognised as the standard corpus in this field. While other corpora, like PropBank, primarily focus on annotating predicate-argument structure, ACE-2005 provides comprehensive information about the overall event structure and semantics. However, its limited language coverage restricts its usability. This paper introduces ACE-2005-PT, a corpus created by translating ACE-2005 into Portuguese, with European and Brazilian variants. To speed up the process of obtaining ACE-2005-PT, we rely on automatic translators. This, however, poses some challenges related to automatically identifying the correct alignments between multi-word annotations in the original text and in the corresponding translated sentence. To achieve this, we developed an alignment pipeline that incorporates several alignment techniques: lemmatization, fuzzy matching, synonym matching, multiple translations and a BERT-based word aligner. To measure the alignment effectiveness, a subset of annotations from the ACE-2005-PT corpus was manually aligned by a linguist expert. This subset was then compared against our pipeline results which achieved exact and relaxed match scores of 70.55\% and 87.55\% respectively. As a result, we successfully generated a Portuguese version of the ACE-2005 corpus, which has been accepted for publication by LDC.

The increasing use of deep learning across various domains highlights the importance of understanding the decision-making processes of these black-box models. Recent research focusing on the decision boundaries of deep classifiers, relies on generated synthetic instances in areas of low confidence, uncovering samples that challenge both models and humans. We propose a novel approach to enhance the interpretability of deep binary classifiers by selecting representative samples from the decision boundary - prototypes - and applying post-model explanation algorithms. We evaluate the effectiveness of our approach through 2D visualizations and GradientSHAP analysis. Our experiments demonstrate the potential of the proposed method, revealing distinct and compact clusters and diverse prototypes that capture essential features that lead to low-confidence decisions. By offering a more aggregated view of deep classifiers' decision boundaries, our work contributes to the responsible development and deployment of reliable machine learning systems., Comment: To be published in the Responsible Generative AI workshop at CVPR

The capabilities of the most recent language models have increased the interest in integrating them into real-world applications. However, the fact that these models generate plausible, yet incorrect text poses a constraint when considering their use in several domains. Healthcare is a prime example of a domain where text-generative trustworthiness is a hard requirement to safeguard patient well-being. In this paper, we present Physio, a chat-based application for physical rehabilitation. Physio is capable of making an initial diagnosis while citing reliable health sources to support the information provided. Furthermore, drawing upon external knowledge databases, Physio can recommend rehabilitation exercises and over-the-counter medication for symptom relief. By combining these features, Physio can leverage the power of generative models for language processing while also conditioning its response on dependable and verifiable sources. A live demo of Physio is available at https://physio.inesctec.pt., Comment: Demo, ECIR 2024, 3rd Sword AI challenge 2023

A tree $t$-spanner of a graph $G$ is a spanning tree $T$ in which the distance between any two adjacent vertices of $G$ is at most $t$. The smallest $t$ for which $G$ has a tree $t$-spanner is called tree stretch index. The $t$-admissibility problem aims to decide whether the tree stretch index is at most $t$. Regarding its optimization version, the smallest $t$ for which $G$ is $t$-admissible is the stretch index of $G$, denoted by $\sigma_T(G)$. Given a graph with $n$ vertices and $m$ edges, the recognition of $2$-admissible graphs can be done $O(n+m)$ time, whereas $t$-admissibility is NP-complete for $\sigma_T(G) \leq t$, $t \geq 4$ and deciding if $t = 3$ is an open problem, for more than 20 years. Since the structural knowledge of classes can be determinant to classify $3$-admissibility's complexity, in this paper we present simpler and faster algorithms to check $2$ and $3$-admissibility for families of graphs with few $P_4$'s and $(k,\ell)$-graphs. Regarding $(0,\ell)$-graphs, we present lower and upper bounds for the stretch index of these graphs and characterize graphs whose stretch indexes are equal to the proposed upper bound. Moreover, we prove that $t$-admissibility is NP-complete even for line graphs of subdivided graphs.

We propose the total staggered quantum walk model and the total tessellation cover of a graph. This model uses the concept of total tessellation cover to describe the motion of the walker who is allowed to hop both to vertices and edges of the graph, in contrast with previous models in which the walker hops either to vertices or edges. We establish bounds on $T_t(G)$, which is the smallest number of tessellations required in a total tessellation cover of $G$. We highlight two of these lower bounds $T_t(G) \geq \omega(G)$ and $T_t(G)\geq is(G)+1$, where $\omega(G)$ is the size of a maximum clique and $is(G)$ is the number of edges of a maximum induced star subgraph. Using these bounds, we define the good total tessellable graphs with either $T_t(G)=\omega(G)$ or $T_t(G)=is(G)+1$. The $k$-total tessellability problem aims to decide whether a given graph $G$ has $T_t(G) \leq k$. We show that $k$-total tessellability is in $\mathcal{P}$ for good total tessellable graphs. We establish the $\mathcal{NP}$-completeness of the following problems when restricted to the following classes: ($is(G)+1$)-total tessellability for graphs with $\omega(G) = 2$; $\omega(G)$-total tessellability for graphs $G$ with $is(G)+1 = 3$; $k$-total tessellability for graphs $G$ with $\max\{\omega(G), is(G)+1\}$ far from $k$; and $4$-total tessellability for graphs $G$ with $\omega(G) = is(G)+1 = 4$. As a consequence, we establish hardness results for bipartite graphs, line graphs of triangle-free graphs, universal graphs, planar graphs, and $(2,1)$-chordal graphs.

A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges, and the tessellation cover number, denoted by $T(G)$, is the size of a smallest tessellation cover. The \textsc{$t$-tessellability} problem aims to decide whether a graph $G$ has $T(G)\leq t$ and is $\mathcal{NP}$-complete for $t\geq 3$. Since the number of edges of a maximum induced star of $G$, denoted by $is(G)$, is a lower bound on $T(G)$, we define good tessellable graphs as the graphs~$G$ such that $T(G)=is(G)$. The \textsc{good tessellable recognition (gtr)} problem aims to decide whether $G$ is a good tessellable graph. We show that \textsc{gtr} is $\mathcal{NP}$-complete not only if $T(G)$ is known or $is(G)$ is fixed, but also when the gap between $T(G)$ and $is(G)$ is large. As a byproduct, we obtain graph classes that obey the corresponding computational complexity behaviors., Comment: 14 pages, 3 figures