de la Banda, Maria Garcia
The divergence time of protein structures modelled by Markov matrices and its relation to the divergence of sequences
Rajapaksa, Sandun, Allison, Lloyd, Stuckey, Peter J., de la Banda, Maria Garcia, Konagurthu, Arun S.
The evolutionary distance between two species is proportional to some (unknown) function of the time of divergence from their common ancestor. One way to estimate this time is by comparing the underlying macromolecular sequences that cascade the information of accumulated evolutionary changes across DNA RNA Proteins (sequence structure function). Since the introduction of the molecular evolutionary clock by Zuckerkandl and Pauling (1965) to perform phylogenetic studies, several statistical models have been proposed to estimate the divergence of extant sequences from common ancestors, and to correlate the estimates of time from other sources of information (e.g., fossil records) when they exist (Sarich and Wilson, 1967). Such divergence time estimates require reliable statistical models of DNA/RNA/Proteins macromolecules (Bromham and Penny, 2003). For protein amino acid sequences, several statistical models have been proposed to explain sequence variation as a function of time. The point accepted mutation (PAM) matrix of Dayhoff et al. (1978) was the first successful model to explain the mutability of amino acid sequences. PAM is a stochastic (Markov) matrix defined in PAM (time) units where PAM-1 is a Markov matrix that embodies a 1% expected change to the amino acids. Subsequent studies highlighted the importance of incorporating evolutionary time-dependent substitution and gap models as an elegant way to model the divergent relationships of proteins (Holmes, 1998; Gonnet et al., 1992). The recent approach of Sumanaweera et al. (2022) derives a unified statistical model for quantifying the evolution of pairs of protein sequences
Position Paper: From Multi-Agent Pathfinding to Pipe Routing
Belov, Gleb, Cohen, Liron, de la Banda, Maria Garcia, Harabor, Daniel, Koenig, Sven, Wei, Xinrui
The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal positions in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance in automated warehousing (such as those operated by Amazon) and in other contemporary application areas. In this paper, we demonstrate that many recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on abstract PR instances. We also discuss further research necessary to tackle real-world pipe-routing instances of interest to industry today. This opens up a new direction of industrial relevance for the MAPF research community.
Redundant Sudoku Rules
Demoen, Bart, de la Banda, Maria Garcia
The rules of Sudoku are often specified using twenty seven \texttt{all\_different} constraints, referred to as the {\em big} \mrules. Using graphical proofs and exploratory logic programming, the following main and new result is obtained: many subsets of six of these big \mrules are redundant (i.e., they are entailed by the remaining twenty one \mrules), and six is maximal (i.e., removing more than six \mrules is not possible while maintaining equivalence). The corresponding result for binary inequality constraints, referred to as the {\em small} \mrules, is stated as a conjecture.