Improved physarum polycephalum shortest path algorithm with preconditioned iterative methods

Keskiner, Hamide Hande
Algorithms for finding the shortest path has many applications in Computer Science, or in other areas of science and engineering. Network optimizations, artificial intelligence and robotics are just a few examples where efficient computation of the shortest path is needed. Various algorithms have been proposed to solve this fundamental problem. Physarum Solver is biologically inspired method that deals with this problem. In the end, a sparse linear system needs to be solved at each iteration of the algorithm. Direct and iterative solvers are two main classes of algorithms for solving sparse linear systems. Direct solvers are robust but they could consume a lot memory due to fill-in. In this thesis, Physarum Polycephalum Shortest Path algorithm is improved using preconditioned iterative methods. We study the convergence behavior as well as memory consumption of various solvers and preconditioners. We show that preconditioned iterative solvers are quite robust and requires much less memory and solution time.


Modelling and predicting binding affinity of PCP-like compounds using machine learning methods
Erdaş, Özlem; Alpaslan, Ferda Nur; Department of Computer Engineering (2007)
Machine learning methods have been promising tools in science and engineering fields. The use of these methods in chemistry and drug design has advanced after 1990s. In this study, molecular electrostatic potential (MEP) surfaces of PCP-like compounds are modelled and visualized in order to extract features which will be used in predicting binding affinity. In modelling, Cartesian coordinates of MEP surface points are mapped onto a spherical self-organizing map. Resulting maps are visualized by using values...
Using collaboration diagrams in component oriented modelin
Tuncel, Mehmet Burhan; Doğru, Ali Hikmet; Department of Computer Engineering (2006)
Component Oriented Software Engineering (COSE) seems to be the future of software engineering. Currently, COSEML is the only modeling language that completely supports the COSE approach. Abstract decomposition of the system and their representing components are shown in a hierarchy diagram to support the COSE process model. In COSEML, only static modeling is supported through this single diagram. However, software is about behavior and static modeling is not sufficient to describe the system. The aim of thi...
Multi-resolution visualization of large scale protein networks enriched with gene ontology annotations
Yaşar, Sevgi; Can, Tolga; Department of Computer Engineering (2009)
Genome scale protein-protein interactions (PPIs) are interpreted as networks or graphs with thousands of nodes from the perspective of computer science. PPI networks represent various types of possible interactions among proteins or genes of a genome. PPI data is vital in protein function prediction since functions of the cells are performed by groups of proteins interacting with each other and main complexes of the cell are made of proteins interacting with each other. Recent increase in protein interactio...
Improved probabilistic decoding of interleaved Reed-Solomon codes and folded Hermitian codes
Özbudak, Ferruh (Elsevier BV, 2014-02-06)
Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher, Kiayias, and Yung is extended to the polynomials whose degrees are allowed to be distinct. Specifically, for a finite field F, positive integers n, r, t and distinct elements z(1), z(2), ... , z(n) is an element of F, we present a probabilistic algorithm which can recover polynomials p(1), p(2), p(r) is an element of F[x] of degree less than k(1), k(2), ... , k(r) respectively for a given instance < y(i), (1, ... ,) y(i,r)>(n)...
Computational representation of protein sequences for homology detection and classification
Oğul, Hasan; Mumcuoğlu, Ünal Erkan; Department of Information Systems (2006)
Machine learning techniques have been widely used for classification problems in computational biology. They require that the input must be a collection of fixedlength feature vectors. Since proteins are of varying lengths, there is a need for a means of representing protein sequences by a fixed-number of features. This thesis introduces three novel methods for this purpose: n-peptide compositions with reduced alphabets, pairwise similarity scores by maximal unique matches, and pairwise similarity scores by...
Citation Formats
H. H. Keskiner, “Improved physarum polycephalum shortest path algorithm with preconditioned iterative methods,” M.S. - Master of Science, Middle East Technical University, 2015.