Zhiliu Zhang, Jiachun Han, and William W. Wells will defend their master's projects and theses this upcoming week.
MASTER'S THESIS DEFENSE: "Rectilinear Steiner Tree Construction"
Zhiliu Zhang
Committee Members: Dr. Jitender Deogun (Advisor), Dr. Ashok Samal and Dr. Vinod Variyam
Friday, November 11, 2016, 1:00 p.m.
347 Avery Hall
Abstract:
The Minimum Rectilinear Steiner Tree (MRST) problem is to find the minimal spanning tree of a set of points (also called terminals) in the plane that interconnects all the terminals and some extra points (called Steiner points) introduced by intermediate junctions, and in which edge lengths are measured in the L1 (Manhattan) metric. This is one of the oldest optimization problems in mathematics that has been extensively studied and has been proven to be NP-complete, thus efficient approximation heuristics are more applicable than exact algorithms.
In this thesis, we present a new heuristic to construct rectilinear Steiner trees (RSTs) with a close approximation of minimum length in O(n log n) time. To this end, we recursively divide a plane into a set of sub-planes of which optimal rectilinear Steiner trees (optRSTs) can be generated by a proposed exact algorithm called Const_optRST. By connecting all the optRSTs of the sub-planes, a suboptimal MRST is eventually constructed.
We show experimentally that for topologies with up to 100 terminals, the heuristic is 1.06 to 3.45 times faster than RMST, which is an efficient algorithm based on Prim’s method, with accuracy improvements varying from 1.31% to 10.21%.
MASTER'S THESIS DEFENSE: "A New Computational System for Human MicroRNA Functional Evaluation and Network Construction"
Jiachun Han
Committee Members: Dr. Juan Cui (Advisor), Dr. Jitender Deogun and Dr. Peter Revesz
Monday, November 14, 2016, 3:30 p.m.
347 Avery Hall
Abstract:
MicroRNAs are functionally important endogenous non-coding RNAs that silence host genes in animal and plant via destabilizing the mRNAs or preventing the translation. Given the far-reaching implication of microRNA regulation in human health, novel bioinformatics tools are desired to facilitate the mechanistic understanding of microRNA mediated gene regulation, their roles in biological processes, and the functional relevance among microRNAs. However, most state-of-the-art computational methods still focus on the functional study of microRNA targets and there is no effective strategy to infer the functional similarity among microRNAs. In this study, we developed a new method to quantitatively measure the functional similarity among microRNAs based on the integrated functional annotation data from Gene Ontology, human pathways, and PFam databases. Through analyzing human microRNAs, we further demonstrated the use of the derived microRNA pairwise similarities to discover the cooperative microRNA modules and to construct the genome-scale microRNA-mediated gene network in human. The complete results and the similarity assessment system can be freely accessed at http://sbbi.unl.edu/microRNASim.
MASTER'S PROJECT DEFENSE: "Unmanned Aerial Vehicle Flight System Failure and Radio Range Analysis"
William W. Wells
Committee Members: Dr. Carrick Detweiler (Advisor), Dr. Justin Bradley and Dr. Byrav Ramamurthy
Tuesday, November 15, 2016, 11:00 a.m.
211 Schorr Center
Abstract:
An increasing global trend is the use of unmanned aerial vehicles (UAV) by hobbyists, researchers, and businesses. Various manufacturers produce their unique UAVs either as assembled models, as a collection of parts requiring assembly, or as a combination of both. There are risks associated with the operation of UAVs. Potential risks include motor failures, lost communications, and abnormal execution times. Vehicle malfunction can be costly. This work closely analyzes the rates and types of failures through repeated flight. A series of tests were devised and conducted to determine the most common physical and cyber failures. Flights were performed indoors using a motion capture system for position estimates while the vehicles were connected to a switching DC power supply to enable quick repetition. Robot Operating System (ROS) was used to parse data received by a connected XBee-Pro and compute a control input that was transmitted to a receiving XBee-Pro on a vehicle. Over 900 total flights using 6 vehicles were performed with over 500 flights performed on a single vehicle for endurance testing. Out of 923 flights 140 (15\%) flights failed. Individual vehicle failure rates ranged from 4-33\%. Time delayed control messages accounted for 125 failures. Communication failures accounted for 8 failures. Hardware failures accounted for 5 failures. Position system lost track of the vehicle on 45 flights.
Most UAVs require radio communication with a ground station. Precise adaptive autonomous control is necessary to enable effective coordination between UAVs. Many manufactures of UAVs use 900 MHz or 2.4 GHz ZigBee radios due to their low cost, low power consumption, and compact form factor. The international XBee-Pros tested have a specification outdoor range of up to 750 m. With a single defective XBee-Pro in a pair of XBee-Pros a range of 140 m outdoors was achieved. Achieving these range limits depends on radio placement and antenna orientation. This initial work is a start on an analysis of the effective range of vertically oriented paired XBee-Pros with two different antenna lengths.