Ugur Dogrusoz  Senior Term Projects

Over the years, senior students have participated in many of our projects leading to useful components of larger software systems (e.g., PATIKA and Chisio), and many methods and algorithms published in leading journals.

Currently available projects and past projects that were successfully completed may be found below.

Objectives

·         Gain experience in software engineering. The students should go through a careful analysis and design phase using the principles of object-oriented paradigm followed by implementation and testing.

·         Get a flavor of doing research and desinging new algorithms.

·         Get involved in large projects to get a “real life” feeling.

·         Learn about the areas of bioinformatics and visualization, and become more familiar with challenges of implementing theoretical algorithms.

Projects

Here are projects available for this academic year:

Facebook Application for Visualizing Social Networks

This application is to construct a visual map of an individual’s friendship network by crawling the Facebook pages. The map should be customized by various options including gender, age, networks, groups and affiliations. The graph constructed from the social network is to be automatically laid out and rendered in line with specified parameters using various visualization techniques. The map should also facilitate navigation to individual’s Facebook pages. This tool is to be unique (see similar applications: Graph My Friends and Groups, Nexus, and Friend Explorer) in its customization abilities.

Graph Visualization Framework for Web Browsers

Many organizations have recently adopted web-based architectures for their software systems. Browser-based thin client architectures provide unified interfaces as well as machine independence. This framework is to provide users with ability to quickly integrate graph visualization components to their browser-based applications. Among operations to be supported are zooming and scrolling over the static graph image produced by the application on the server side (similar to Google Maps). In addition, the users should be able to inspect graph objects (e.g. nodes). This requires accurate hit-testing of nodes with varying shapes, which is not avaiable in Google Maps.

Visual Aid for Web Surfing

When surfing the web, one can easily get lost, making the process of backtracking to the pages that are more helpful to the surfer difficult. Perhaps this is not as such a major problem for web sites that are well-organized (some web sites even offer a site map for this purpose) if you are to navigate within a single web site, say http://www.bilkent.edu.tr. However, this is more often not the case than it is.

This project involves developing a visual aid for the surfer to maintain a "mental map" of the part of the web that has been recently surfed, through the help of a dynamic site map (a graph where nodes represent the web pages visited recently, and edges the links among these pages).

Apart from the fact a graph model is needed to represent the map of the currently encountered parts of web and displaying this with a Java applet on a browser page, the challenge in accomplishing this is to draw this map/graph in an easily understandable way. Remember that the site map we are interested in drawing is not static, and will constantly change as the user surfs. Luckily, there are automatic graph layout algorithms that can be implemented for this purpose.

Tool for Constructing Web Site Maps

In this project, you are to write a tool that can detect a web site's contents and present it as a map (i.e., a graph). The aim is to provide a web site designer with facilities to visually inspect the structure and content of the web site, so they can improve its structure and content. For instance, broken links or pages that are “too many links away” from home could be detected (and shorter links could be introduced).

For instance, when http://www.bilkent.edu.tr is chosen, the tool is to discover all the pages in the same domain that can be reached from the home page of this site automatically and form a graph of these pages using their links as the graph's edges.

Similarly, you are to use automatic graph layout to layout the graph before presenting to the user.

Bioinformatics

2004/5          PATIKA

·         Development of PATIKAweb: [3-5 students] This project involves design and implementation of a thin web client (applet) for querying and visualizing biological pathway data available in the PATIKA database. This client is to provide a quick and easy access to the knowledge in the database, not requiring any registration or installation of software.

·         Developlement of  the Client/Server Architecture for PATIKApro: [3-5 students] This project involves design and implementation of the client/server architecture of the PATIKApro software. The architecture is crucial for efficient communication of PATIKApro clients with the PATIKA database and server components (e.g., query and data submission managers).

·         Graph Algorithms for Advanced Querying in PATIKApro: [3-5 students] This project involves design and implementation of algorithms for advanced querying of a pathway database. The new pathway model in PATIKApro requires more advanced querying (graph traversal) techniques to handle compoung graph structures and such.

2003/4          PATIKApro

·         Design and Implementation of New Methods for Analysis of Microarray Data within PATIKApro Using Existing Pathway Data: [1 student] This project involves design and implementation of new methods for analysis of microarray data within PATIKApro using existing pathway data. Benefits might include inference of pathway data and pathway activity information.

·         Graph Algorithms for Pathway Layout and Advanced Querying in PATIKApro: [2 students] This project involves design and implementation of algorithms for pathway layout. The algorithm needs to be able to handle compound graph structures existing in pathway graphs of PATIKApro.  The new pathway model in PATIKApro requires more advanced querying (graph traversal) techniques to handle compoung graph structures and such.

2002/3           PATIKApro

·         User Management: [3 students] This project involves design and implementation of user management in PATIKApro.

2001/2           PATIKA

Some projects involving collaboration with Molecular Biology and Genetics department include development of new components as well as improvements to the existing components of the PATIKA tool. PATIKA is a software tool for storing, constructing, querying, visualization, and manipulation of regulatory cell pathways:

·         Cell Pathway Layout: [2 students] This project involves design and implementation of algorithms for the layout of cell pathways. Cell pathways are directed graphs with several different types of nodes and edges and with positioning (compartment) constraints.

·         Query Algorithms: [1-3 students] This project involves design and implementation of query algorithms to extract the desired information from PATIKA’s database, which contains all pathways pre-stored for a particular organism, as desired by the PATIKA users. These queries lead to directed and/or undirected (dcpending on the type of the query) graph algorithms since the PATIKA database is essentially a huge graph containing all available molecule-to-molecule interactions within the particular organism’s cell. Variation of existing graph algorithms such as shortest paths, calculation of a certain neighborhood of a subgraph, etc. would be needed to be designed and implemented to be able to answer such queries.

·         Scripting Language: [2-3 students] This project involves the design and implementation of a scripting language for the PATIKA editor. The PATIKA editor is a GUI based client side application through which researchers construct, manipulate, query, and visualize the cell pathways. The scripting language should allow one to perform the same operations as the editor in a batch manner or from the command line.

·         Simulation Support: [2-3 students] This project involves the design and implementation for the simulation of signaling transduced in cell pathways. Simulation involves determining proper conditions for presence of each particular state of a molecule in the cell and highlighting the transduction that takes place visually within the PATIKA editor framework.

·         Data Mining: [2-3 students] This project involves mining of the literature on cell pathways to extract the the molecule-to-molecule interactions automatically or semi-automatically. One of the most challenging tasks in realizing PATIKA’s potential is to fill in its database with as much information available as possible, and doing this completely manually would be very cumbersome and inefficient.

2000/1          Reconstruction of Phylogenetic Trees

This is a general problem in biology. It is used in molecular biology to help understand the evolutionary relationships among proteins, for example. The project involves implementation and possibly improvement of existing algorithms for comparing given species and algorithms for using the comparison results for construction a tree to infer the evolutionary history of current organisms. It also involves use of Tom Sawyer's Graph Editor Toolkit for visualizing the constructed tree.

Graph Visualization

2001/2           Abstract Formal Machine Simulator

The project is to port an existing software written in C and X windows environmnet to Java and improve its useful interface (i.e., visualization capabilities). The software tool was developed for visualizing the computations of automata models such as

·         Finite State Automata

·         One-Way Finite State Automata

·         Deterministic Two-Way Finite State Automata

·         Deterministic Push Down Automata

·         Deterministic Linear Bounded Automata

·         Deterministic Turing Machine

·         Deterministic Single-Tape Turing Machine

·         Deterministic Multi-Tape Turing Machine

·         Deterministic Multi-Track Turing Machine

·         Deterministic Two Dimensional-Tape Turing Machine

·         LL(k) Parser

·         LR(k) Parser

for educational purposes.

The tool was implemented in C programming language under Sun Unix 4.1.1. operating system, and extensively uses X Toolkit Intrinsics and Athena Widget Set.

The system is menu-driven. Upon the choice of the user, the user is prompted to enter the definition of the machine s/he has selected. After entering the definition, the next step is choosing the simulation mode (step or continuous) and entering the input (usually a string of symbols). After that, the user may start the simulation and observe the behaviour of the machine throughout the simulation.

2000/1          UML Diagram Editing and Layout

The project is to develop a UML diagram editor (class and activity diagrams), which also facilitates auto-layout of such diagrams. It involves using Tom Sawyer's Graph Editor Toolkit, and customizing it for UML diagrams as well as designing and implementing algorithms for layout of such diagrams.

1999/0           Visual Aid Tools for Web Surfing

World Wide Web has gotten to be enormous over the past few years. Similarly, navigating through the web (aka surfing) has become more and more popular as useful information out there (as well as junk, sadly) has increased dramatically. The following projects are aimed at helping a web browser in the surfing process.

Dynamic site map:

When surfing the web, one can easily get lost, making the process of backtracking to the pages that are more helpful to the surfer difficult. Perhaps this is not as such a major problem for web sites that are well-organized (some web sites even offer a site map for this purpose) if you are to navigate within a single web site, say http://www.bilkent.edu.tr. However, this is more often not the case than it is.

This project involves developing a visual aid for the surfer to maintain a "mental map" of the part of the web that has been recently surfed, through the help of a dynamic site map (a graph where nodes represent the web pages visited recently, and edges the links among these pages).

Apart from the fact a graph model is needed to represent the map of the currently encountered parts of web and displaying this with a Java applet on a browser page, the challenge in accomplishing this is to draw this map/graph in an easily understandable way. Remember that the site map we are interested in drawing is not static, and will constantly change as the user surfs. Luckily, there are automatic graph layout algorithms that can be implemented for this purpose.

Detecting a web site's map:

In this project, you are to write a tool that can detect a web site's contents and present it as a map (i.e., a graph). For instance, when http://www.bilkent.edu.tr is chosen, the tool is to discover all the pages in the same domain that can be reached from the home page of this site automatically and form a graph of these pages using their links as the graph's edges.

Similarly, you are to use automatic graph layout to layout the graph before presenting to the user.

Combinatorial Optimization

2002/3           Ordered One-Dimensional Compaction for Polyominoes

This project involves design and implementation of algorithms for ordered one-dimensional compaction of polyominoes to use in incremental layout of disconnected graphs.