Abstract The use of Graphics Processing Units to accelerate computational applications is increasingly being adopted due to its affordability, flexibility and performance. However, achieving top performance comes at the price of restricted data-parallelism models. In the case of sequence alignment, most GPU-based approaches focus on accelerating the Smith-Waterman dynamic programming algorithm due to its regularity. Nevertheless, because of its quadratic complexity, it becomes impractical when comparing long sequences, and therefore heuristic methods are required to reduce the search space. We present GPUGECKO, a CUDA implementation for the sequential, seed-and-extend sequence-comparison algorithm, GECKO. Our proposal includes optimized kernels based on collective operations capable of producing arbitrarily long alignments while dealing with heterogeneous and unpredictable load. Contrary to other state-of-the-art methods, GPUGECKO employs a batching mechanism that prevents memory exhaustion by not requiring to fit all alignments at once into the device memory, therefore enabling to run massive comparisons exhaustively with improved sensitivity while also providing up to 6x average speedup w.r.t. the CUDA acceleration of BLASTN.

MOTIVATION: Molecular docking is aimed at predicting the conformation of small-molecule (ligands) within an identified binding site (BS) in a target protein (receptor). Protein-ligand docking plays an important role in modern drug discovery and biochemistry for protein engineering. However, efficient docking analysis of proteins requires prior knowledge of the BS, which is not always known. The process which covers BS identification and protein-ligand docking usually requires the combination of different programs, which require several input parameters. This is furtherly aggravated when factoring in computational demands, such as CPU-time. Therefore, these types of simulation experiments can become a complex process for researchers without a background in computer sciences. RESULTS: To overcome these problems, we have designed an automatic computational workflow (WF) to process protein-ligand complexes, which runs from the identification of the possible BSs positions to the prediction of the experimental binding modes and affinities of the ligand. This open-access WF runs under the Galaxy platform that integrates public domain software. The results of the proposed method are in close agreement with state-of-the-art docking software. AVAILABILITY AND IMPLEMENTATION: Software is available at: https://pistacho.ac.uma.es/galaxy-bitlab. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Motivation: Nearly 10 years have passed since the first mobile apps appeared. Given the fact that bioinformatics is a web-based world and that mobile devices are endowed with web-browsers, it seemed natural that bioinformatics would transit from personal computers to mobile devices but nothing could be further from the truth. The transition demands new paradigms, designs and novel implementations. Results: Throughout an in-depth analysis of requirements of existing bioinformatics applications we designed and deployed an easy-to-use web-based lightweight mobile client. Such client is able to browse, select, compose automatically interface parameters, invoke services and monitor the execution of Web Services using the service's metadata stored in catalogs or repositories. Availability and implementation: mORCA is available at http://bitlab-es.com/morca/app as a web-app. It is also available in the App store by Apple and Play Store by Google. The software will be available for at least 2 years. Contact: [email protected]. Supplementary information: Source code, final web-app, training material and documentation is available at http://bitlab-es.com/morca.

It is becoming clear that most human diseases have a complex etiology that cannot be explained by single nucleotide polymorphisms (SNPs) or simple additive combinations; the general consensus is that they are caused by combinations of multiple genetic variations. The limited success of some genome-wide association studies is partly a result of this focus on single genetic markers. A more promising approach is to take into account epistasis, by considering the association of multiple SNP interactions with disease. However, as genomic data continues to grow in resolution, and genome and exome sequencing become more established, the number of combinations of variants to consider increases rapidly. Two potential solutions should be considered: the use of high-performance computing, which allows us to consider a larger number of variables, and heuristics to make the solution more tractable, essential in the case of genome sequencing. In this review, we look at different computational methods to analyse epistatic interactions within disease-related genetic data sets created by microarray technology. We also review efforts to use epistatic analysis results to produce biomarkers for diagnostic tests and give our views on future directions in this field in light of advances in sequencing technology and variants in non-coding regions.

Motivation: The identification and accurate description of large genomic rearrangements is crucial for the study of evolutionary events among species and implicitly defining breakpoints. Although there is a number of software tools available to perform this task, they usually either a) require a collection of pre-computed non-conflicting High Scoring Pairs (HSPs) and gene annotations or involve working at protein level (which excludes non-coding regions); or b) need many parameters to adjust software behavior and performance; or c) imply working with duplications, repeats and tandem repeats, which complicates the identification of rearrangements task. Although there are many programs specialized in the detection of these repetitions, they are not designed for the identification of main genomic rearrangements. Methods: The methodology we envisage starts with the detection of all HSPs by pairwise genome comparison. The second step involves solving conflicts generated by fragments that overlap in both sequences (double-overlapped fragments) to end yielding a collection of gapped fragments. In the third step, the quality measures (length, score, identities) of the gapped fragment are refined by using a modified dynamic programming approach. This collection of refined gapped fragments represents the input of a recursive process in which we identify blocks of gapped fragments that maintain co-localization, regardless of them occurring in coding or non-coding regions. The identification of interspersed repeats is an important step in the subsequent refinement of these blocks. This step allows for the separation of repetitions and the correct identification in turns of longer blocks. Finally, groups of interspersed repeats, duplications, inversions and translocations are identified. Results: The set of algorithms presented in this manuscript is able to detect and identify blocks of large rearrangements -tacking into account interspersed repeats, tandem repeats and duplications starting with the simple collection of un gapped local alignments. To the best of our knowledge, this is the first method to approach the whole process as a coherent workflow -thus outperforming current state-of-the-art software tools while it allows to classify the type of rearrangement. The results obtained are an important source of information for breakpoint refinement and featuring, as well as for the estimation of the evolutionary event frequencies to be used in inter-genome distance proposals, etc. Data sets and Supplementary Material are available at: http://bitlab-es.comlgecko-csb/.

BACKGROUND: Conventional pairwise sequence comparison software algorithms are being used to process much larger datasets than they were originally designed for. This can result in processing bottlenecks that limit software capabilities or prevent full use of the available hardware resources. Overcoming the barriers that limit the efficient computational analysis of large biological sequence datasets by retrofitting existing algorithms or by creating new applications represents a major challenge for the bioinformatics community. RESULTS: We have developed C libraries for pairwise sequence comparison within diverse architectures, ranging from commodity systems to high performance and cloud computing environments. Exhaustive tests were performed using different datasets of closely- and distantly-related sequences that span from small viral genomes to large mammalian chromosomes. The tests demonstrated that our solution is capable of generating high quality results with a linear-time response and controlled memory consumption, being comparable or faster than the current state-of-the-art methods. CONCLUSIONS: We have addressed the problem of pairwise and all-versus-all comparison of large sequences in general, greatly increasing the limits on input data size. The approach described here is based on a modular out-of-core strategy that uses secondary storage to avoid reaching memory limits during the identification of High-scoring Segment Pairs (HSPs) between the sequences under comparison. Software engineering concepts were applied to avoid intermediate result re-calculation, to minimise the performance impact of input/output (I/O) operations and to modularise the process, thus enhancing application flexibility and extendibility. Our computationally-efficient approach allows tasks such as the massive comparison of complete genomes, evolutionary event detection, the identification of conserved synteny blocks and inter-genome distance calculations to be performed more effectively.

The cost of obtaining genome-scale biomedical data continues to drop rapidly, with many hospitals and universities being able to produce large amounts of data. Managing and analysing such ever-growing datasets is becoming a crucial issue. Cloud computing presents a good solution to this problem due to its flexibility in obtaining computational resources. However, it is essential to allow end-users with no experience to take advantage of the cloud computing model of elastic resource provisioning. This paper presents a workflow that allows the end user to perform the core steps of a genome wide association analysis, consisting of 1) uploading raw data files to the cloud, 2) genotype calling, i.e. converting the raw data into information on genome variation 3) quality assessment of the genotype data and subsequent filtering based on user-provided parameters and 4) downloading the filtered genotype data in a standard file format. A number of steps in this process are computationally intensive; moreover, the computational resources involved vary greatly depending on the size of the study, from a few samples to a few thousand. Therefore cloud computing provides an ideal solution to this problem. The paper describes in detail how the pipeline was implemented, focussing on the cloud infrastructure and the different tools and software involved for software management and GUI construction. The key contributions of this paper are: 1a) iIt presents a real world application of cloud-computing to address a critical problem in biomedicine, . 2b) iIt provides a thorough description of how such a pipeline was implemented, in terms of data management and user-interface, such that the end-user does not need to focus on the computational aspect but can instead concentrate on data analysis and biological interpretation of results, and. c3) wWe show how cloud-computing can be used in a more effective way through the parallelisation of the appropriate parts of the pipeline.

The petabyte scale of the Big Data generation in bioinformatics requires the introduction of advanced computational techniques to enable efficient knowledge discovery from data. Many data analysis tools in bioinformatics have been developed but few have been adapted to take advantage of high performance computing (HPC) resources. For some of these tools, an attractive option is to employ a map/reduce strategy. On the other hand, Cloud Computing could be an important platform to run such tools in parallel because it provides on-demand, elastic computational resources. This paper presents a software suite for Microsoft Azure which supports legacy software (without modifications of the algorithm). We demonstrate the feasibility of the approach by benchmarking a typical bioinformatics tool, namely dotplot.

Ultra high density oligonucleotide microarrays allow several millions of genetic markers in a single experiment to be observed. Current bioinformatics software for gene expression quantile data normalization is unable to process such huge datasets. In parallel with this perception, the huge volume of molecular data produced by current high-throughput technologies in modern molecular biology has increased at a similar pace the challenge in our capacity to process and understand data. On the other hand, the arrival of CUDA has unveiled the extraordinary power of Graphics Processors (GPUs) to accelerate data intensive general purpose computing more and more as times goes by. This work takes these two emerging trends to benefit side by side during the development of a high performance version for a biomedical application of growing popularity: gene expression normalization. A variety of experimental issues are analyzed for this execution, including cost, performance and scalability of the graphics architecture on three different platforms. Our study reveals advantages and drawbacks of using the GPU as target hardware, providing lessons to benefit a broad set of existing genetic applications, either based on those pillars or having similarities with their procedures.

BACKGROUND: Bioinformatics is commonly featured as a well assorted list of available web resources. Although diversity of services is positive in general, the proliferation of tools, their dispersion and heterogeneity complicate the integrated exploitation of such data processing capacity. RESULTS: To facilitate the construction of software clients and make integrated use of this variety of tools, we present a modular programmatic application interface (MAPI) that provides the necessary functionality for uniform representation of Web Services metadata descriptors including their management and invocation protocols of the services which they represent. This document describes the main functionality of the framework and how it can be used to facilitate the deployment of new software under a unified structure of bioinformatics Web Services. A notable feature of MAPI is the modular organization of the functionality into different modules associated with specific tasks. This means that only the modules needed for the client have to be installed, and that the module functionality can be extended without the need for re-writing the software client. CONCLUSIONS: The potential utility and versatility of the software library has been demonstrated by the implementation of several currently available clients that cover different aspects of integrated data processing, ranging from service discovery to service invocation with advanced features such as workflows composition and asynchronous services calls to multiple types of Web Services including those registered in repositories (e.g. GRID-based, SOAP, BioMOBY, R-bioconductor, and others).

Abstract Motivation: Web services technology is becoming the option of choice to deploy bioinformatics tools that are universally available. One of the major strengths of this approach is that it supports machine-to-machine interoperability over a network. However, a weakness of this approach is that various Web Services differ in their definition and invocation protocols, as well as their communication and data formats—and this presents a barrier to service interoperability. Results: jORCA is a desktop client aimed at facilitating seamless integration of Web Services. It does so by making a uniform representation of the different web resources, supporting scalable service discovery, and automatic composition of workflows. Usability is at the top of the jORCA agenda; thus it is a highly customizable and extensible application that accommodates a broad range of user skills featuring double-click invocation of services in conjunction with advanced execution-control, on the fly data standardization, extensibility of viewer plug-ins, drag-and-drop editing capabilities, plus a file-based browsing style and organization of favourite tools. The integration of bioinformatics Web Services is made easier to support a wider range of users. Availability and Implementation: jORCA binaries and extended documentation are freely available at http://www.bitlab-es.com/jorca under the Creative Commons Attribution-No Derivative Works 2.5 Spain License and jORCA source code (implemented in Java) is available under request. (GPL v3 license). jORCA has been tested under UNIX (Fedora 11, open SUSE 11 and Ubuntu 8.1), MS-Windows and Mac OS 10.5 operating systems. Java VM version 1.6.0 later is required. Contact: [email protected] or [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

BACKGROUND: Nowadays, microarray gene expression analysis is a widely used technology that scientists handle but whose final interpretation usually requires the participation of a specialist. The need for this participation is due to the requirement of some background in statistics that most users lack or have a very vague notion of. Moreover, programming skills could also be essential to analyse these data. An interactive, easy to use application seems therefore necessary to help researchers to extract full information from data and analyse them in a simple, powerful and confident way. RESULTS: PreP+07 is a standalone Windows XP application that presents a friendly interface for spot filtration, inter- and intra-slide normalization, duplicate resolution, dye-swapping, error removal and statistical analyses. Additionally, it contains two unique implementation of the procedures - double scan and Supervised Lowess-, a complete set of graphical representations - MA plot, RG plot, QQ plot, PP plot, PN plot - and can deal with many data formats, such as tabulated text, GenePix GPR and ArrayPRO. PreP+07 performance has been compared with the equivalent functions in Bioconductor using a tomato chip with 13056 spots. The number of differentially expressed genes considering p-values coming from the PreP+07 and Bioconductor Limma packages were statistically identical when the data set was only normalized; however, a slight variability was appreciated when the data was both normalized and scaled. CONCLUSION: PreP+07 implementation provides a high degree of freedom in selecting and organizing a small set of widely used data processing protocols, and can handle many data formats. Its reliability has been proven so that a laboratory researcher can afford a statistical pre-processing of his/her microarray results and obtain a list of differentially expressed genes using PreP+07 without any programming skills. All of this gives support to scientists that have been using previous PreP releases since its first version in 2003.

BACKGROUND: To aid in bioinformatics data processing and analysis, an increasing number of web-based applications are being deployed. Although this is a positive circumstance in general, the proliferation of tools makes it difficult to find the right tool, or more importantly, the right set of tools that can work together to solve real complex problems. RESULTS: Magallanes (Magellan) is a versatile, platform-independent Java library of algorithms aimed at discovering bioinformatics web services and associated data types. A second important feature of Magallanes is its ability to connect available and compatible web services into workflows that can process data sequentially to reach a desired output given a particular input. Magallanes' capabilities can be exploited both as an API or directly accessed through a graphic user interface.The Magallanes' API is freely available for academic use, and together with Magallanes application has been tested in MS-Windows XP and Unix-like operating systems. Detailed implementation information, including user manuals and tutorials, is available at http://www.bitlab-es.com/magallanes. CONCLUSION: Different implementations of the same client (web page, desktop applications, web services, etc.) have been deployed and are currently in use in real installations such as the National Institute of Bioinformatics (Spain) and the ACGT-EU project. This shows the potential utility and versatility of the software library, including the integration of novel tools in the domain and with strong evidences in the line of facilitate the automatic discovering and composition of workflows.

BACKGROUND: Array-based comparative genome hybridization (aCGH) is commonly used to determine the genomic content of bacterial strains. Since prokaryotes in general have less conserved genome sequences than eukaryotes, sequence divergences between the genes in the genomes used for an aCGH experiment obstruct determination of genome variations (e.g. deletions). Current normalization methods do not take into consideration sequence divergence between target and microarray features and therefore cannot distinguish a difference in signal due to systematic errors in the data or due to sequence divergence. RESULTS: We present supervised Lowess, or S-Lowess, an application of the subset Lowess normalization method. By using a predicted subset of array features with minimal sequence divergence between the analyzed strains for the normalization procedure we remove systematic errors from dual-dye aCGH data in two steps: (1) determination of a subset of conserved genes (i.e. likely conserved genes, LCG); and (2) using the LCG for subset Lowess normalization. Subset Lowess determines the correction factors for systematic errors in the subset of array features and normalizes all array features using these correction factors. The performance of S-Lowess was assessed on aCGH experiments in which differentially labeled genomic DNA fragments of Lactococcus lactis IL1403 and L. lactis MG1363 strains were hybridized to IL1403 DNA microarrays. Since both genomes are sequenced and gene deletions identified, the success rate of different aCGH normalization methods in detecting these deletions in the MG1363 genome were determined. S-Lowess detects 97% of the deletions, whereas other aCGH normalization methods detect up to only 60% of the deletions. CONCLUSION: S-Lowess is implemented in a user-friendly web-tool accessible from http://bioinformatics.biol.rug.nl/websoftware/s-lowess. We demonstrate that it outperforms existing normalization methods and maximizes detection of genomic variation (e.g. deletions) from microbial aCGH data.

MOTIVATION: In addition to existing bioinformatics software, a lot of new tools are being developed world wide to supply services for an ever growing, widely dispersed and heterogeneous collection of biological data. The integration of these resources under a common platform is a challenging task. To this end, several groups are developing integration technologies, in which services are usually registered in some sort of catalogue to allow novel discovering and accessing mechanisms to be implemented. However, each service demands specific interfaces to accommodate their parameters and it is a complicated task linking the different service inputs and outputs to solve a biological problem. RESULTS: In this work we address the design and implementation of a versatile web client to access BioMOBY compatible services (a system by which a client can interact with multiple sources of biological data regardless of the underlying format or schema) using the service description stored in the BioMOBY catalogue. The automatic interface generator significantly reduces developing time and produces uniform service access mechanisms. The design and proof of concept (for such a client) including the generic interface generator have been developed and implemented in the National Institute for Bioinformatics in Spain. AVAILABILITY: The INB (National Institute for Bioinformatics, Spain) platform is available at www.inab.org/MOWServ

BACKGROUND: Microarray technology is generating huge amounts of data about the expression level of thousands of genes, or even whole genomes, across different experimental conditions. To extract biological knowledge, and to fully understand such datasets, it is essential to include external biological information about genes and gene products to the analysis of expression data. However, most of the current approaches to analyze microarray datasets are mainly focused on the analysis of experimental data, and external biological information is incorporated as a posterior process. RESULTS: In this study we present a method for the integrative analysis of microarray data based on the Association Rules Discovery data mining technique. The approach integrates gene annotations and expression data to discover intrinsic associations among both data sources based on co-occurrence patterns. We applied the proposed methodology to the analysis of gene expression datasets in which genes were annotated with metabolic pathways, transcriptional regulators and Gene Ontology categories. Automatically extracted associations revealed significant relationships among these gene attributes and expression patterns, where many of them are clearly supported by recently reported work. CONCLUSION: The integration of external biological information and gene expression data can provide insights about the biological processes associated to gene expression programs. In this paper we show that the proposed methodology is able to integrate multiple gene annotations and expression data in the same analytic framework and extract meaningful associations among heterogeneous sources of data. An implementation of the method is included in the Engene software package.

Abstract In this work we present an architecture for XML‐based mediator systems and a framework for helping systems developers in the construction of mediator‐services for the integration of heterogeneous data sources. A unique feature of our architecture is its capability to manage (proprietary) user's software tools and algorithms, modelled as Extended Value Added Services (EVASs), and integrated in the data flow. The mediator offers a view of the system as a single data source where EVASs are readily available for enhancing query processing. A Web‐based graphic interface has been developed to allow dynamic and flexible EVASs inter‐connection, thus creating complex distributed bioinformatics machines. The feasibility and usefulness of our ideas has been validated by the development of a mediator system (Bio‐Broker) and by a diverse set of applications aimed at combining gene expression data with genomic, sequence‐based and structural information, so as to provide a general, transparent and powerful solution that integrates data analysis tools and algorithms. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract We present a novel application of knowledge discovery technology to a developing and challenging application area such as bioinformatics. This methodology allows the identification of relationships between low‐magnitude similarity (LMS) sequence patterns and other well‐contrasted protein characteristics, such as those described by database annotations. We start with the identification of these signals inside protein sequences by exhaustive database searching and automatic pattern recognition strategies. In a second step we address the discovering of association rules that will allow tagging sequences that hold LMS signals with consequent functional keywords. We have designed our own algorithm for discovering association rules, meeting the special necessities of bioinformatics problems, where the patterns we search lie in sparse datasets and are uncommon and thus difficult to locate. Computational efficiency has been verified both with synthetic and real biological data showing that the algorithm is well suited to this application area compared to state of the art algorithms. The usefulness of the method is confirmed by its ability to produce previously unknown and useful knowledge in the area of biological sequence analysis. In addition, we introduce a new and promising application of the rule extraction algorithm on gene expression databases.

SUMMARY: AnaGram is a web service for protein function assignment based on identity detection of small significant fragments (protomotifs) that can act as modular pieces in peptide construction. The system is able to assign function by finding correlations between protomotifs and functional annotations contained in SWISS-PROT and Medline databases. In addition, function ontologies are used for hierarchical organization of the predicted functions. Extensive tests have been carried out to evaluate the accuracy and performance of the system. AVAILABILITY: http://jaguar.genetica.uma.es/anagram.htm

We present a video content analysis and metadata organizational system for research videos arising from biological microscopy of living cells. Automated procedures are described to determine the position, size, shape and orientation of cells in each video frame. From the temporal changes in the values of these simple metadata parameters, high-level descriptors are derived that describe the semantic content of the video. This content information (specific intrinsic metadata) is of high information value, since it describes the behavior of cells and the timing of events within the video, including changes in environmental conditions experienced by the cells. When such metadata are properly organized in a searchable database, a content-based video query and retrieval system may be developed to locate particular objects, events or behaviors. Moreover, the availability of such semantic contents in the formal and generic format we propose will allow the application of data mining techniques and the amassing of more elaborate knowledge, e.g., species classification depending on behavior, patterns in response to environment changes, etc. The suitability and functionality of the proposed metadata model is demonstrated by the automated analysis of five different types of biological experiments, recording epithelial wound healing, bacterial multiplication, the rotations of tethered bacteria, and the swimming of motile bacteria and of human sperm.

UNLABELLED: PreP is a versatile, powerful, standalone application that aims at pre-processing gene expression data. AVAILABILITY: Documentation and executable file for MS-Windows are available at http://chirimoyo.ac.uma.es/bitlab/services/index.htm

Abstract Summary: Engene is a versatile, and platform-independent web tool for exploratory analysis of gene expression data that aims at storing, visualizing and processing large sets of gene expression patterns. Availability: Access to engene is available on request at http://www.engene.cnb.uam.es Contact: [email protected] * To whom correspondence should be addressed.

Abstract Scientific computing has traditionally been done on workstations, most of the time running on UNIX‐like operating systems. These systems are often very robust, powerful and especially suited to heavy computation tasks; however, the usual user interface is based on a command line with all the information needed for the appropriate functioning of the algorithm. These command lines are seldom user‐friendly but, on the other hand, they allow batch processes to be built. In this work, a model for command‐line‐driven packages is given, and at the same time the model includes objects that can be directly translated into a graphical user interface. A language (Colimate) implementing this model is shown to serve as a bridge between command‐line‐driven programs and more friendly user interfaces. Exploiting the specificness of the user interfaces addressed, powerful graphical interfaces can be built with a very simple syntax and small programming effort. Furthermore, the command‐line program needs not to be modified, so in this way the possibility of making batches is not lost. Copyright © 2002 John Wiley & Sons, Ltd.

It is known that while the programs used to find genes in prokaryotic genomes reliably map protein-coding regions, they often fail in the exact determination of gene starts.This problem is further aggravated by sequencing errors, most notably insertions and deletions leading to frame-shifts.Therefore, the exact mapping of gene starts and identification of frame-shifts are important problems of the computer-assisted functional analysis of newly sequenced genomes.Here we review methods of gene recognition and describe a new algorithm for correction of gene starts and identification of frame-shifts in prokaryotic genomes.The algorithm is based on the comparison of nucleotide and protein sequences of homologous genes from related organisms, using the assumption that the rate of evolutionary changes in protein-coding regions is lower than that in non-coding regions.A dynamic programming algorithm is used to align protein sequences obtained by formal translation of genomic nucleotide sequences.The possibility of frame-shifts is taken into account.The algorithm was tested on several groups of related organisms: gamma-proteobacteria, the Bacillus/Clostridium group, and three Pyrococcus genomes.The testing demonstrated that, dependent on a genome, 1-10 per cent of genes have incorrect starts or contain frame-shifts.The algorithm is implemented in the program package Orthologator-GeneCorrector.

We present a video analysis and content-based video query and retrieval system for research videos arising from biological microscopy that: (a) uses image processing procedures to identify objects and events automatically within the digitized videos, thus leading to the generation of content information (specific intrinsic metadata) of high information value by automated analysis of their visual content; and (b) permits subsequent queries to be performed on the specific intrinsic metadata thus generated, allowing important factual and analytical information to be obtained and selected video sequences matching the query criteria to be retrieved. Such a system requires the novel use of image and video processing techniques, and new approaches to the organization, accessing and querying of video metadata databases.

MOTIVATION: The explosive growth of the biological sequences databases stimulated by genome projects has modified the framework of several applications in the biological sequence analysis area. In most cases, this new scenario is characterized by studies on large sets of sequences, suggesting the need for effective and automatic methods for their clustering. A more effective clustering of the database could be followed by the application of common family analysis schemes to the groups so formed. RESULTS: In this work, we present a new strategy to reduce the computational cost associated with the clustering of large sets of sequences which are expected to contain several families. The strategy is based on the grouping of the sequences into families by using a dynamic threshold on a pairwise sequence similarity criterion. Routine clustering of large data sets can now be done very efficiently. The method developed here achieves a computational space reduction of about an order of magnitude over more traditional ones of all-versus-all comparisons. The outcome of this approach produces family groupings that reproduce closely already accepted biological results. Our work includes a parallel implementation for distributed memory multiprocessors with a dynamic scheduling strategy for performance optimization. AVAILABILITY: By anonymous ftp at ftp.ac.uma.es (/pub/ots/pCluster directory), or from our Web site http://www.cnb. uam.es/www/software/software_index.html CONTACT: [email protected]

SUMMARY: This note describes the parallelization of a key biological application, such as the construction of phylogenetic trees, using the DNAml program. A careful run-time analysis allowed us to propose an efficient parallelization that scaled very well to large problem sizes. AVAILABILITY: By anonymous ftp at ftp.ac.uma. es (/pub/ots/pDNAml) or from our web site http://www.cnb.uam. es/www/software/software_index.html CONTACT: [email protected]

We present an approach to the study of the relationships between biological sequences and structures applying image analysis methods to dotplots. We introduce a set of analytical tools based on different types of digital image-processing filters that are new within the context of dotplots. We have reformulated some of the usual approaches in dotplot analysis as mathematical operations on images within the framework of mathematical morphology. An X-Window-based implementation of this new approach has been developed and is available by anonymous FTP.

We present a new parallel computing approach to the case of exhaustive sequential sequence comparison algorithms on message-passing architectures. In this context a modification of guided self-scheduling as well as efficient buffering strategies are presented. We discuss two specific implementations, one on the Paramid parallel computer, and the other on a cluster of workstations running PVM. In both cases the parallel performance is higher than with any other method presented so far. The code is public domain and can be obtained by anonymous ftp at ftp.cnb.uam.es.