Development of novel algorithms and software library for biomedical engineering application

BioInfFast

Development of novel algorithms and software library for biomedical engineering application

DNAproject

About

The aim of this project is to develop a new algorithms for DNA alignment, search and clustering, new recommendation algorithm for collaborative health care and use of different meta-heuristic algorithms for biomedical engineering applications. We plan to create a software library that will consists of existing and new designed algorithms.

Description

Development of a novel algorithm for DNA alignment, search and clustering.

In recent years, several successful applications of data mining techniques for solving biological problems have been reported. Some examples of analyzing large data sets and inferring structure are: prediction of protein structure, gene classification, clustering of gene expression data, statistical modeling of protein-protein interaction, etc. Some common activities in bioinformatics that benefit from using information techniques are mapping and analyzing DNA and protein sequences, aligning DNA and protein sequences and creating 3-D models of protein structures.

Currently in the field of bioinformatics there is an urgent need of algorithms for DNA alignment, search and clustering, as well as optimization of the existing ones. In this activity, firstly we will try to develop and implement novel algorithms for DNA local pairwise alignment. Namely, the time inefficiency has been the major disadvantage of current known local pairwise alignment techniques. Despite the time complexity, space complexity is often found as a limiting factor when aligning large nucleotide sequences. In order to reduce space complexity of an alignment, methodology presented in (D. STOJANOV et al. [6]) represents each region of consecutive matching nucleotides with a triple, identifying region’s length and starting positions at the sequences. Based on this representation, measurements performed in [6] clearly show that linear space is required, while the time complexity is O(nm2). Most of the time in [6] is wasted on examining all combinations of un-gapped local alignments within overlapping sections and the number of alignments being examined. When aligning similar nucleotide sequences, large regions of consecutive matching nucleotides are part of the optimal un-gapped local alignment. Also, the probability of finding an optimal un-gapped local alignment within m–nucleotides long overlapping sections is higher than the probability of finding it in overlapping sections with less than m nucleotides, where m is the length of the smaller nucleotide sequence, subject of an alignment.

Thus, the aim of this activity is development of fast local alignment generating methodology, requiring linear time and space – O(m), when aligning approximately same size, similar nucleotide sequences.

We are going to work with data mining algorithms, that can be applied to gene finding, protein function domain detection, function motif detection, protein function inference, disease diagnosis, disease prognosis, disease treatment optimization, protein and gene interaction network reconstruction, etc.

Development of a novel recommendation algorithm for collaborative health care

The recent trend in healthcare support systems is the development of patient-centric pervasive environments in addition to the hospital-centric one. Pervasive health care takes steps to design, develop, and evaluate computer technologies that help citizens participate more closely in their own healthcare, on one hand, and on the other to provide flexibility in patients’ active everyday life with work, family and friends. In the framework of this working package mathematical model of a novel algorithm that generates recommendations and suggestions for preventive intervention instead of emergency care and hospital admissions is planned to be developed. The main purpose of this algorithm is to find the dependence between users’ health condition and performed physical activities. In this way, the proposed algorithm should generate recommendations that will help the user to adapt his physical activities in order to improve his own health. These recommendations should also encourage users to lead an active life filled with physical activities and thus become direct participants in maintaining their own health care.

The main purpose of this algorithm is to find the dependency of the users’ health condition and physical activities they perform. The algorithm will incorporate collaboration and classification techniques in order to generate recommendations and suggestions for preventive intervention. To achieve this, we will consider datasets from the health history of users and use classification algorithms on these datasets for grouping the users based on their similarity. Use of classified data when generating the recommendation provides more relevant recommendations, because they are enacted on knowledge for users with similar medical conditions and reference parameters.

There are a number of parameters that might be used to characterize a person. They are all mainly continuous variables and they are measured with (near) continuous resolution. On the other hand, the bio-medical parameters and phenomena are often too complex and too little understood to be modelled analytically. Because of its continuous nature, the fuzzy systems are very close to the medical reality and at the same time, fuzzy sets allow natural description of bio-medical variables using symbolic models and their formalisms, avoiding the analytical modelling.

Therefore, in our algorithm, fuzzy sets and fuzzy discretization will be considered as a suitable approach that can bridge the gap between the discrete way reasoning in the IT systems and the continuity of biomedical parameters. The proposed algorithm will be implemented within the library and validated using generic data. The results of this validation will be presented and conclusions will be derived.

Implementation of meta-heuristic algorithms for biomedical engineering applications

In this action several meta-heuristic algorithms will be implemented with emphasis on their application in solving optimization biomedical engineering problems. The following algorithms will be developed: genetic algorithms, ant-colony, particle swarm optimization and harmony search.

Genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.

Ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. This algorithm is a member of the ant colony algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations. The initial idea was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants.

Particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. PSO optimizes a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formulae over the particle's position and velocity. Each particle's movement is influenced by its local best known position and is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.

Harmony search (HS) is a phenomenon-mimicking algorithm inspired by the improvisation process of musicians. Nowadays, music-inspired phenomenon-mimicking harmony search algorithm is fast growing with many applications. One of key success factors of the algorithm is the employment of a novel stochastic derivative which can be used even for discrete variables. Instead of traditional calculus-based gradient, the algorithm utilizes musician’s experience as a derivative in searching for an optimal solution. This can be a new paradigm and main reason in the successes of various applications.

-
Design and implementation of software library for biomedical applications

The last activity of this project foresees implementation of all the previously developed algorithms and their integration into a single software library. In this activity the architecture of the library will be designed first. Two architecture models will be evaluated: three-tier and MVC as possible solutions. The main aim of this activity will be to produce an architecture model that will enable plug-and-play possibilities for various independent modules implementing various algorithms and providing the same mathematical foundation for all of them. Moreover, the library will be designed so, that it will enable various interfaces towards the end-users applications.