Search

The unordered tree edit distance is a natural metric to compute distances between trees without intrinsic child order, such as representations of chemical molecules. While the unordered tree edit distance is MAX SNP-hard in principle, it is feasible for small cases, e.g. via an A* algorithm. Unfortunately, current heuristics for the A* algorithm assume unit costs for deletions, insertions, and replacements, which limits our ability to inject domain knowledge. In this paper, we present three novel heuristics for the A* algorithm that work with custom cost functions. In experiments on two chemical data sets, we show that custom costs make the A* computation faster and improve the error of a 5-nearest neighbor regressor, predicting chemical properties. We also show that, on these data, polynomial edit distances can achieve similar results as the unordered tree edit distance., Accepted at the 14th International Conference on Similarity Search and Applications (SISAP 2021)

Additional file 1: Supplementary material describing: S1 Quickload server, S2 Patterns inferred from ChromHMM, S3 Sub-patterns found, S4 Nearest gene annotation, S5 Functional annotations, S6 Annotation from tracks, S7 DNA loops, and related References.

Nowadays, Big Data platforms allow the analysis of massive data streams in an efficient way. However, the services they provide are often too raw, thus the implementation of advanced real-world applications requires a non-negligible effort for interfacing with such services. This also complicates the task of choosing which one of the many available alternatives is the most appropriate for the application at hand. In this paper, we present a comparative study of the three major open-source Big Data platforms for stream processing, as performed by using our novel RAM^3S framework. Although the results we present are specific for our use case (recognition of suspect people from massive video streams), the generality of the RAM^3S framework allows both considering such results as valid for similar applications and implementing different use cases on top of Big Data platforms with very limited effort.

Biologists generally interrogate genomics data using web-based genome browsers that have limited analytical potential. New generation genome browsers such as the Integrated Genome Browser (IGB) have largely overcome this limitation and permit customized analysis to be implemented using plugins. We extend the functionality of IGB with two plugins which allow to enable molecular, network and structure biology, and to perform advanced pattern search in the genome browser tracks. 3D interactomes (networks of molecular interactions, which structures are either known or modeled) facilitate the identification of disease-relevant interactions that can then be specifically targeted by drugs. We developed a plugin for IGB, that uses advanced visualization techniques to integrate the analysis of genomics data with network and structural biology approaches. The plugin automatically maps genomic regions to protein sequence and interaction structures and identifies residues in contact with proteins, nucleic acids or small molecules. This allows the end user to generate hypotheses regarding drug- and ligand-dependent perturbations of PPI networks, and provides predictions as to how specific mutations might have an impact on drug resistance. We also integrated a pattern-search algorithm to provides biologists with the ability, once they identify an interesting genomic pattern, to look for similar occurrences in the data, thus facilitating genomic data access and use. For example, such patterns can describe gene expression regulatory DNA areas including heterogeneous (epi)genomic features (e.g. histone modification and/or different transcription factor binding regions). It is possible to define complex patterns based on perfect matches in genome tracks (regions that must match), partial matches (regions that are allowed to be absent), and negative matches (for instance to search for regions distant from transcription start sites). Plugins available at: http://cru.genomics.iit.it/igbmibundle/ and http://www-db.disi.unibo.it/research/GenData/SimSearch

Next Generation Sequencing (NGS), with the high amount of heterogeneous data that it is generating, is opening many interesting practical and theoretical computational problems. Genome browsers, e.g. UCSC Genome Browser (Kuhn et al., 2013) or Integrated Genome Browser (IGB) (Nicol et al., 2009), allow visual inspection and identification of interesting patterns on multiple genome browser tracks, i.e. of sets of (epi)genomic regions/peaks at given distances from each other in different tracks. For example, such patterns can describe gene expression regulatory DNA areas including heterogeneous (epi)genomic features (e.g. histone modification and/or different transcription factor binding regions). Yet, once such patterns are visually identified in a genome section, the search of their occurrences along the whole genome is a complex computational task that is currently not supported, despite their discovery along the whole genome is very important for the biological interpretation of NGS experimental results and comprehension of biomolecular phenomena. We defined an optimized pattern-search algorithm able to find efficiently, within a large set of (epi)genomic data, genomic region sets which are similar to a given pattern. We implemented it within an IGB plugin, which allows intuitive user interaction in both the visual selection of an interesting pattern on the loaded IGB tracks, and the visualization of occurrences of similar patterns identified along the entire genome.

With the amount of heterogeneous data that Next Generation Sequencing (NGS) is producing, many interesting computational problems are emerging and call for urgent solutions. Genome Browsers (e.g., IGB) are tools to visually compare and browse through multiple genomic feature samples aligned to the same genome reference and laid out on different genome browser tracks. They allow the visual inspection and identification of interesting “patterns” on multiple tracks, i.e. sets of genomic regions/peaks at given distances from each other in different genome browser tracks. Nevertheless, once such patterns are visually identified in a genome section, the search of their occurrences along the whole genome is a complex computational task currently not supported, although their discovery along the whole genome is very important for the biological interpretation of NGS experimental results and comprehension of biomolecular phenomena. To overcome such limitation, we present an optimized “similarity”-based pattern-search algorithm able to efficiently find, within a large set of genomic data, genomic region sets which are similar to a given pattern. We implemented our algorithm within an IGB plugin, which allows intuitive user interaction in both the visual selection of an interesting pattern on the loaded IGB tracks and the visualization within the IGB of the occurrences along the entire genome of the region sets similar to a selected pattern found by our algorithm. This demonstrates the efficiency and the accuracy of the proposed method.

Authorship attribution is the science of inferring characteristics of an author from the characteristics of documents written by the author herself/himself. It represents a problem with a long history and a wide range of applications. Recent works in non-traditional authorship attribution domains demonstrate the practicality of automatic analysis of documents based on authorial style. Such analyses are difficult to apply, little is known about types or rates of error, and few best practices are available. In this paper, we show how quantitative techniques based on image similarity search can be profitably exploited for revealing forgery of handwritten corpora. More in details, we explore the case where a document is represented by means of the image of the document itself. Preliminary experimental results conducted on real data and run on a software implementation of the proposed solution, namely WRITINGSIMILARITYSEARCH (WSS), demonstrate the effectiveness of our document classifier and encourage further investigations on this direction.