Sharif Digital Repository

The Steiner forest problem is one of the most fundamental issues in network design that emerges in various contexts, such as the design of communication networks,transportation networks, VLSI circuits and phylogenetic network reconstruction. In this problem, we are given a connected weighted undirected graph and a special subset of vertices that are partitioned in pairs. The goal is to fnd a minimum-cost sub-graph in which each special vertex is connected to its mate. In this thesis we review a set of selected solutions for this problem and a few other related problems.For example, we study modeling and solving the s-t shortest path problem in order to gain insight into current Steiner... 

In minimum cut problem we aim at finding a set of edges with minimum overall cost possible, such that removing them would separate two specific vertices, source and sink. This problem has been studied thoroughly, however the available algorithms were not proven to be time-wise optimal. Nowadays, planar graphs have attracted more attention because of their applications in cities and countries map. Moreover,their characteristics and properties, make some problems easier to solve in planar case. In this thesis, we will have a survey on algorithms for minimum cut on planar graphs. Our motivation to choose these algorithms is the balance between how easily they could be implemented and how fast... 

Multiplicative weight update method, is an statistical method to produce approximation algorithms. These algorithms have applications in various fields, including: Graph Algorithms, Machine learning, Optimization, Computational geometry, Game theory, etc.Recently, with this method, fast approximation algorithms have been created for many problems, including, solving linear programming. Here, we try to study this method and it’s applications, in detail  

Cancer can be defined as a stochastic phenomenon. Thus, the tumor growth can be defined as a stochastic process. A Cancer tumor can be analyzed by its geometric shape. Furthermore, computing fractal dimension of shapes is a useful technique to analyze chaosity and complexity of shapes. This approach can be used to compare results from laboratory with simulated results of a mathematical model. A stochastic model of tumor growth will be presented. And some geometrical properties will be analyzed through computer simulation of the model  

Evolutionary processes are the process of change in one or more physical and heritable characteristics that result from the occurrence of genetic changes (beneficial, harmful, or neutral) over time, and ultimately from generation to generation, depending on natural selection. Cancer is a genetic disease that occurs as a result of an evolutionary process by the somatic cells and examining the spatial characteristics of cancer can help understanding it. It is also important to examine the spatial configuration of cells considering their access to limiting factors such as nutrients and adequate space. In addition, paying attention to the gene expression, individually and collectively, will help... 

The aim of this thesis is to review the theory of deep learning with an experimental approach. In this thesis, we review researches that examine the impact of input selection on outputs in deep learning systems; Inputs we can control (samples, architecture, model size, optimizer, etc.) and outputs we can observe (the performance of the neural network, its test error, its parameters, etc.). Among the reviewed cases are the generalizability of deep learning systems, the effect of model components on its accuracy, interpolation and hyperparameters, as well as new phenomena in this field for which new frameworks have been defined  

Online problems were first introduced in 1980s due to process the data arise from the internet. An Online algorithm is an algorithm which takes a part of input at each step and should give an irrevocable answer before entrance of the rest of data. Online problems are considered when the size of the input is substantial or there are time limitations to wait for the whole input to arrive. One of the first online algorithms discussed was the online bipartite matching. In this problem there exists a bipartite graph with one offline part which is present from the beginning and nodes of the other part entering one by one with all of their corresponding edges. At the entrance of each node the... 

One of the most important targets in bio-informatics is the analysis of biological networks. These networks are modeled by graphs. Comparing networks with mapping is a useful tool for analyzing. The mapping between the nodes of a network that preserves some topological and functional structures, is called network alignment. Network alignment has various applications in different fields; such as pattern recognition, social networks, biological networks, and etc. The alignment of the protein-protein interaction network is one of the substantial problems. There are many static algorithms for the alignment of PPI networks. Because of the developments of computer science in recent years,... 

The field of Genome-Wide Asocciation Studies (GWAS) plays a vital role in understanding the genetic basis of complex traits and diseases. In this thesis, the focus is on investigating the effectiveness of two approaches combining Differential Evolution (DE) with Random Forest (RF) and support vector machine (SVM) for feature selection in the context of GWAS. Arabidopsois Thaliana dataset is used as experimental dataset for comparative analysis. The main goal is to achieve more efficient feature selection while maintaining competitive accuracy compared to RF and SVM without using DE. This research includes conducting experiments using DE with RF and DE with SVM followed by a comprehensive... 

One of the most available genomics data in Iran is non-invasive parental testing (NIPT) data obtained from the blood of pregnant mothers after the tenth week of pregnancy using the new generation sequencing technology. Sequencer output is a combination of maternal and fetal read data, most of which (about 90%) is from maternal DNA. These data have very low coverage of the genome, but their advantage is that they read the entire human genome. Low coverage data has led to the loss of large parts of the genome, but having a large number of samples helps to compensate for this problem. The purpose of this project is to use this data with the help of imputation methods to build a reference for... 

Colorectal cancer (CRC) is one of the most common cause of cancer death worldwide. Identification of pivot genes in colorectal cancer can play an important role as biomarkers in predicting and early diagnosis and reducing the number of deaths caused by this disease. In this study, the aim of which is to discover pivot genes in colorectal cancer, six microarray datasets selected from the GEO database including 277 tumor tissue samples and 325 normal colon tissue samples. After data processing, differentially expressed genes and CRC-related genes were screened and 285 shared genes between them were identified for subsequent analysis. Based on 285 shared genes, the protein-protein interaction... 

The ”Secretary Problem” is an easy model of online decision making unedr uncertainty, in which a small company intends to hire a new employee. It interviews with the applicants and after each interview, it should make a decision based on the information of the interviewees seen so for and without any knowledge of further applicants. The goal is to design a strategy of decision making with which the probability of choosing the best one is maximized.The secretary problem is not restricted to the issue of hiring an employee. It is advantageous in various areas such as economy,management, marriage and etc. The span of its utility makes it an intriguing problem that attracts the attention of many... 

One of the most important problems in online learning is a prediction with expert advice. In each step we make our prediction not only based on previous observation but also use expert information. In this thesis, we study the different well-known algorithms of expert advice and generalize problems when data arrival is in the two-dimensional grid. regret is a well-studied concept to evaluate online learning algorithm. online algorithm when data arrive consecutively in T time step has regret O (√(T)) . regret in two-dimensional grid with T row and P column is O(T√(P)).
2010 MSC: 68Q32 ; 68T05 ; 90C27  

Genetic heterogeneity within a tumor, which occurs during cancer evolution, is one of the reasons for treatment failure and increased chances of drug resistance. Cancer cells initially derive from a mutated progenitor cell, resulting in shared mutated genes. Throughout the course of tumor formation and progression, the occurrence of new mutations is possible, leading to the generation of cancer cells with various mutated genes. An appropriate approach is to identify the sequence of mutations that have occurred in the tumor, which can be inferred from single-cell sequencing data. Singlecell data provides valuable information about branching events in the evolution of a cancerous tumor. In... 

The main objective of all managers of the economic organizations, manufacturing and industrial companies and service providers is to take steps toward improvement and effective use of different resources like workforce, capital, materials, energy and information. To attain the desired productivity, managers have to observe requirements such as establishment of a working organizational structure, effective implementation methods, safe equipment and tools, balanced working atmosphere and qualified human force as the most important factor. Therefore productivity culture should be publicized throughout the organization, and human force should be considered as the main component of this process.... 

Considering the advantages of optical communications and code division multiple access technique, Optical Code Division Multiple Access Networks (OCDMANs) was introduced. Thence, many researchers have suggested methods for creating Quality of Service (QoS) differentiated classes in OCDMANs. In this thesis, we have comprehensive review on the QoS assignment methods and enhance them by offering new techniques. In physical layer, we concentrate on variable chip rate OCDMANs and in MAC sub-layer, a new algorithm named Adaptive Level Control (ALC) is introduced. Then, we focus on the physical design of OCDMANs. Firstly, we solve the problem of one-class OCDMAN and introduce few simple and... 

Consistent growth in volume and dynamic behavior of traffic mandates new requirements for fast and adaptive resource allocation in modern optical networks.Elastic optical networks have been proposed to provide a competitive and scalable solution by creating tunable high-capacity optical communication networks in which network elements are configured according to the actual need to minimize resource usage for the specified service requirements. Resource allocation with quality of service constraints is one of the most challenging problems in elastic optical networks which is conventionally formulated as a complex mixed-integer nonlinear optimization program.In this research work, we focus on... 

In this study, integrated navigation systems that utilize velocity-matching algorithm and are used in automatic landing of Unmanned Aerial Vehicles (UAV) are investigated. At first, the accuracy of the navigation system in the landing phase is analyzed and the relationship between the accuracy of inertial sensors, flight parameters and the accuracy of the navigation system is derived analytically. Then, by integrating the dynamic model of the UAV and the inertial measurement unit, a new algorithm for navigation of fixed-wing UAVs is presented. The integration mechanism of the proposed algorithm is tightly coupled; hence, it is capable to eliminate the errors of UAV model and inertial system.... 

The perpuse of this thesis is to design and fabricate a laboratory one degree of freedom stable platform under turbulences by model-based design method. To do this, different parts of the system were first modeled in the Solidworks software and then fabricated with various tools. With proper assembly of electronic and mechanical components, the original body of the system was created. Then, the controller motor with a stable platform which is attached to it was modeled and simulated in MATLAB software. Then, the parameters of the equations were calculated using standard identification tests and TCACS optimization algorithm. One of the challenges of this thesis is the malfunction of the...