Deutschland online bookmaker 100% Bonus.

Download Template Joomla 3.0 free theme.

Thesis Defenses 2012

Finding the pattern of homologous genes location in prokaryotic genomes

By: Mahdi Heidari
Supervisors: Dr. Ali Moeini , Dr. Mehdi Sadeghi
Co-Advisor: Dr. Ruzbeh Tusserkani

Defense room: Engineering Science 1
Committee: Dr. Kambiz Badie, Dr. Abbas Nozari
Date: Tuesday, January 3, 2012

Abstract: One of the fundamental problems in bioinformatics is phylogenetic reconstruction, which is classifying living organisms into different taxonomic clades. The classical approach for this problem is based on using 16S ribosomal RNA similarities. In recent years, much effort has been made to find other methods, as reconstruction of a phylogenetic tree based on a single gene may not end in proper results. In practice, using whole genome content might be a good idea. With the increasing availability of fully-sequenced genomes, gene order can be considered as a new solution for phylogenetic tree reconstruction. In the present work, we applied “common intervals” in two or more genomes to infer their distance and to create their phylogenetic tree. We tested this method on a dataset of 63 prokaryotes with known COGs. Similarity between the reconstructed phylogenetic tree by our method and the phylogenetic tree obtained from NCBI taxonomy browser is as high as 92%. We show that this approach outperforms most of the currently available methods based on gene orders. Also we offered a new algorithm for finding maximal common intervals in two general sequences, it's Run time complexity is from O(n2), and uses linear memory usage. In contrast with present best algorithm(CI), our algorithm needs less memory space however its run time complexity is similar to CI. One other advantages of our algorithm is, its extensibility. We can run this algorithm with parallel CPU, and this feature has not been seen in previous algorithms.

Keywords: Phylogenetic tree reconstruction, Gene order, Common interval finding algorithm, Parallel algorithm, comparative genomics, bioinformatics

On thin tree of bounded tree-width and parallel series graphs

By: Saeed Akhoondian Amiri
Supervisors: Dr. Dara Moazzami
Co-Advisor: Dr. Ali Moeini

Defense room: Engineering Science 1
Committee: Dr. Kambiz Badie, Dr. Mohammad Ganj Tabesh
Date: Tuesday, January 3, 2012

Abstract: In this thesis we introduce thin tree, which is useful for approximating travelling salesman problem. At first glance seems thin tree in bounded tree-width graph is solvable in linear time, But by searching on similar problems, we can see it’s not as easy as other problems.
Currently NP-Hardness of finding thin tree is not clear, but we showed that finding thinness of special spanning tree is NP-Hard; also we found some good thin tree in bounded genus graphs. Also we apply another algorithm to find thin tree in Series-Parallel graphs with bounded degree.

Keywords: Tree-width, Approximation algorithms, Travelling salesman problem, Thin Tree, Parallel Series graphs, bounded tree-width graph

Evaluating algorithms for Facility Location Improved Algorithms for Facility Location and K-median and some other problems

By: Sara Rohani
Supervisor: Dr. Ali Moeini
Advisor: Dr. Mohammad Ali Safari

Defense room: Faculty of Engineering conference room
Committee: Dr. Kambiz Badie, Dr. Morteza Mohammad Nozari
Date: Saturday, February 18, 2012

Abstract: In these thesis different variants of Facility Location Problem (FLP) has been investigated. FLP as a subject of the field of Operation Research has been studied widely in recent fifteen years by researchers. Many approaches have been applied to FLP, such as: Local Search, Linear Programming, Approximation Algorithms, Heuristic Algorithms and many others. Our focus is on improvement of Greedy Algorithms and reverses Greedy Algorithms for FLP. We have applied the improved Reverse Greedy Algorithm on FLP and K-Median Problem. In Reverse Greedy Algorithm, we have changed the greedy decision parameter. In our new algorithm, we have tried to determine the greedy decision parameter according to average service costs and distances, and make decision according to the coefficient of the part of any request in whole costs. In both problems, we have presented the results of our tests in the groups, classified by the standard deviation of the cost of nodes and edges. In groups with lower standard deviation, the results are near to optimal solution. The growth in standard deviation causes the difference between results and optimal solution. In both problems, the time of running the algorithms has got better than the previous version. Because of our good choice in proper parameters, in uniform distributions the results are good. We have proposed a problem named K-Request that has never been studied before. We have applied the Greedy Algorithm with average parameter on it. We have studied the Weighted FLP and proved that it is as difficult as Standard FLP. We have studied and modeled a fire station in a region of Tehran, and measured its optimality. In our results, it was 1.5 times the optimal.

Keywords: Facility Location, K-Median, Greedy Algorithm, Reverse Greedy Algorithm

A sociologically-inspired distributed clustering method for sensor networks

By: Ardeshir Baharian
Supervisors: Dr. Majid Nili Ahmadabadi, Dr. Babak Najar Araabi

Defense room: Engineering Science 1
Committee: Dr. Kambiz Badie, Dr. Mohammad Reza Javadi Yeganeh
Date: Monday, February 27, 2012

Abstract: Wireless sensor networks have drawn the world's attention recently. These networks are formed of a large number of sensors that can sense the environment. In addition, they are able to save and process data and also to send the information via wireless network transmitters. Due to the physical attributes of sensors, these networks are facing crucial challenges like low battery power, limited rate of sending and receiving data, cooperation with other sensors, network scalability and etc. Recently, several solutions have been presented to order and manage sensors to overcome these problems. One solution is to group sensors into clusters and to transfer the whole information. Therefore, the clustering issue in sensor networks is a common issue. In recent years, much research has been done on this matter and successful ways have been released to solve the problem.
In this research, our aim is to offer a new way to cluster the sensor network. Thus, we tried to take advantage of concepts in social science and human interactions. To achieve this aim, two perspectives have been considered. The former is a top-bottom view inspired by the behavior of imperialist countries and the competition among them. To achieve it, we used the Imperialist Competition Algorithm (ICA) and then converted it to a competitive cluster formation algorithm. This method does not give better results in comparison to former ways, but it seems to be useful with better outputs in case of continuance of research process.
The latter is a bottom-top view inspired by the human behavior of participating in a friendship group. In our opinion, the issue of forming friendship groups and selecting group leaders is very similar to clustering in a sensor network. Hence, a novel algorithm for clustering sensor networks is proposed on the basis of human behavior model in human societies. Finally, the results show that the proposed method is always better than a network with no clustering. And also, in most cases, it gives better results than other available clustering methods.


By: Hamed Nazaktabar
Supervisors: Dr. Majid Nili Ahmadabadi, Dr. Kambiz Badie

Defense room: Engineering Science 1
Committee: Dr. Babak Nadjar Aarabi, Dr. Mohammad Reza Meybodi
Date: Monday, February 27, 2012

Abstract: Using wireless sensor networks has significantly increased in recent years. These networks contain many sensors. These sensors can sense the environment, save and process information and send data via the wireless network transceiver. The limitation of the sensor’s power supply source is one of the most challenging issues in WSNs. Generally, data transfer and computing are two most energy consuming activities in sensors. Many researches have done in this area and each has improved less or more the state of the art.
In many applications, sensors need to send the approximation of the read data. In these applications, it has been shown that using predictive models reduces the number of data transfers as it guarantees the accuracy of data. This reduction depends on environment’s signal and its changing trend. Also, the model's characteristics have significant effects on transferred data volume. Till now, various models have been applied to signal prediction in wireless sensor networks, like "Probabilistic models", "Time-series models" and "Kalman Filter model". The main drawbacks of these models are high computational order and their need for too many parameters for model updating. Regarding to the dynamics of environment, needing few parameters for updating, is an essential feature of these sorts of models.
In this research, we aim to design a predictive model which has significant forecasting power, while it needs as less as possible data for updating, according to WSNs features. The "RLSP" (Reinforcement Learning based Signal Predictor) algorithm, presented in this research, is designed to satisfy these criteria based on Reinforcement Learning. This algorithm learns the environment signal and extracts the model of signal based on its experiences. Simultaneously, this model is used to make prediction. To evaluate, we have simulated our algorithm in MATLAB and compared our results to the Time-series algorithms. The simulation results show that RLSP algorithm has superior performance in approximately all signals. Moreover, it shows good efficiency in prediction.

Next Webpage Prediction Based On Web Usage Mining

By: Mohammad Chamanpara
Supervisor: Dr. Kambiz Badie

Defense room: Engineering Science 3
Committee: Dr. Ali Moeini, Dr. Mirhossein Pedram
Date: Monday, August 4, 2012

Abstract: Web personalization is the process of customizing the web, based on the needs of a particular user, using the knowledge obtained from the analysis of user navigation behavior in conjunction with other information collected from the website structure, content, and user profile. Due to the explosive growth of the Web, the web personalization domain in both research and commercial development has increased dramatically. In this thesis, a rule based and also collaborative method presented in which the rules of the rule-based system are association rules and the process of recommending web pages to users will be done fully automated. In this approach, the system does not receive any information from users explicitly and user profiles are generated automatically. Much time consuming operations in this method can be performed offline and after user login, the recommendation action will be done in a short time. Other users’ choices are used for improving the recommendation. It also is equipped with a learning algorithm that learns rules over the user's interests and use then in further recommendations.

Keywords: web personalization, recommender systems, web customizing, frequent pattern mining, association rule mining.

Analysis of protein domain decomposition problem via graph theory

By: Sajad Mirzaei
Supervisors: Dr. A. Moeini, Dr. M. Sadeghi

Defense room: Engineering Science 3
Committee: Dr. Kambiz Badie, Dr. Abbas Nozari
Date: Saturday, August 4, 2012

Abstract: Proteins usually consist of domain structures which have an important role in their classification and analysis. Since their number is increasing in an exponential rate, computer aided and automatic methods for protein domain decomposition are essential. Also, experimental methods in laboratories are expensive and time consuming.
Protein's structure is easily convertible to a graph from its fundamental atoms. So, implementation of graph approaches is highly recommended. One of applicable methods in protein domain decomposition is the min-cut problem.
In this thesis, first we review existing methods in protein domain decomposition, then we analyze the implementation of min-cut problem in this concept. Furthermore, we compare three min-cut methods with different approaches, and after their implementation in protein domain decomposition problem, we present results and analysis of them.

Maximum common substructure extraction in RNA secondary structures using clique detection approach

By: Mina Akhavan
Supervisor: Dr. Mehdi Sadeghi, Dr. Ali Moeini
Co-Advisor: Dr. Fatemeh Zare

Defense room: Engineering Science 4
Committee: Dr. Kambiz Badie, Dr. Abbas Nozari
Date: Monday, September 3, 2012

Abstract: In this thesis maximum common substructure extraction problem in multiple RNA secondary structures has been investigated with a new approach and an algorithm based clustering has been presented for this problem.
It has been realized that RNA performs a wide range of functions in biological system and therefore comparing the similarities of RNA secondary structures is one of the challenging tasks in molecular biology as similar structures often imply similar functions.
In recent years, most existing tools represent the secondary structures by tree-based presentation and calculate the similarity by tree alignment distance. In this thesis maximum common substructure extraction problem has been reduced to maximum clique detection problem. Clearly for this reducing, it’s essential that primary graphs that represent RNA secondary structures convert to new data structures that clique problem is applicable for them. After implementation and result analysis has been proved when we increase the number of RNA secondary structures in the exact algorithm due to the high runtime, algorithm was impractical.
For solving this problem in new algorithm we use clustering solutions. The clustering algorithm that has been used in my thesis is UPGMA.
One of the most important sections in this algorithm is that we must can rollback to primary structures after finding maximum clique in new data structure. It means that with regarding current clique we can specify common substructures in RNA secondary structures.

Graph Analysis of 3-dimensional Structure of Extremophile Proteins for Detection and Discrimination of Proteins in Different Classes

By: Elham Nikookar
Supervisor: Dr. Kambiz Badie, Dr. Mehdi Sadeghi

Defense room: Engineering Science 1
Committee: Dr. Ali Moeini, Dr. Abbas Nozari
Date: Tuesday, September 18, 2012

Abstract: Many scientific efforts have been done on using machine learning techniques for development of classification algorithms that in recent years these efforts have been focused more on the concept of ensemble learning. In ensemble learning, results of different classification algorithms are combined to produce more accurate and robust results.
A novel ensemble algorithm for discriminating different extremophile proteins is proposed in this thesis from which we used to investigate extracted features of protein sequence and protein three dimensional structure. Unlike most ensemble methods in which training samples are divided into some subsets, we grouped original dataset into some subgroups based on original features. Each subgroup consists of all samples based on only a subset of features. The main idea of this thesis is using weak learners which each of them becomes expert on a subset of features. The idea of using weak learners, not only results to some sort of dimensionality reduction of feature vector, but also accelerates the process of learning and classification because of a parallel mechanism of weak learners. Performance of proposed method is evaluated using protein data bank dataset which is a free to use dataset and the results are compared to other state of the art algorithms. Not only the proposed method produces more accurate results than traditional machine learning algorithms, but also it is more robust than other well-known ensemble methods and its performance is comparable to famous and efficient algorithms.

Keywords: Bioinformatics, Machine learning, Ensemble learning, Classification, Extremophile proteins, Weak learner, Protein sequence, three dimensional structure.

Using Stochastic Petri Nets to Improving Prognosis in Preventive Maintenance

By: Seyed Mohammad Reza Farahy
Supervisor: Dr. Ali Moeini
Adviser: Dr. Masoud Rabbani

Defense room: Engineering Science 10
Committee: Dr. Amin Ghoddousian, Dr. Hassan Haghighi
Date: Wednesday, October 3, 2012

Abstract: An compatible modeling for a manufacturing system tries that it can response to increasing demands on system safety and performance, and economic maintenance under growing degree of systems automation and complicated. So, this is most important that we have high availability of service with cost optimization, especially for systems concerned by wear and ageing.
In this paper, we present a discrete modeling by stochastic Petri nets (SPN) of the repairable systems. This modeling has been used of the state of wear and ageing records of the equipment in order to advance failure prediction. Likewise, improvement of failure-prediction related to analysis the event data of before occur failures in the repairable systems, it is by our modeling supported too.
When performance of a piece of equipment or a system degraded to a certain degree, preventive maintenance actions must be taken to restore it in order to ensure normal operation. We are assumed that repots of equipment state will be ready by equipment signal states. Change failure rate are considered simultaneously in order to determine the firing factor of a SPN. Consequently, SPN can predictive each failure that may occur as soon as, with the type of failure by lowest cost of system maintenance. SPN have real-time characteristics, they can be applied effectively to simulate manufacturing procedures and to respond to maintenance situations in real-time.
Our research has demonstrated that stochastic Petri Nets (SPNs) may be successfully applied for modeling of failure-prediction in repairable systems. The predictive process was structured after analysis event data and then a modeling by stochastic Petri Nets (SPNs) created and corresponding failures places modeled using software jPNS Tools. Our tests on a simulated repairable system show that the obtained results are reasonable and the probability of failure rate has an important role to failure sequence place of SPN and safety of systems. This means that the SPNs may be used as a decision support system for failure-prediction.

Keywords: preventive maintenance, Petri nets, event data, manufacturing system

Submodularity in Combinatorial Optimization

By: Salman Fadaei
Supervisors: Dr.Ali Moeini
Co-Advisor: Dr.Mohammad Ali Safari

Defense room: Engineering Science 1
Committee: Dr. Dara Moazzami, Dr. Yahya Tabesh
Date: Monday, September 6, 2010

Abstract: Recently, Submodularity has attained an important role in computer science fields. The problems of maximizing submodular set functions are NP-hard, and, consequently, to tackle these kinds of problems we need to find effective approximation algorithms.
In this thesis, at first we had a survey on the methods used for the maximization problems and then by applying innovative methods, we achieved some faster algorithms or algorithms with better approximation ratios. Our most important results are as follows:

  • Maximizing non-monotone submodular functions subject to a cardinality or an exact cardinality constraint. In this case, we achieved simpler and faster algorithms.
  • Maximizing non-monotone submodular functions with respect to a cardinality constraint or constant number of cardinality constraints. Here, we achieved a better approximation factor.
  • Maximizing non-monotone submodular functions subject to any solvable packing polytope. This problem has not been considered before and we found the first constant approximation factor for the problem.

Keywords: Submodular set functions, Maximization, Non-monotone, Knapsack, Polytope, Matroid