Skip to main content
Kent State University Home

Open Access Kent State (OAKS)

  • About
    • About
    • Frequently Asked Questions
    • Rights and Reuse
  • Browse
    • Authors
    • Collections
    • Communities
    • Subjects
  • Login

PHYSICAL DNA MAPPING AND PROPER INTERVAL GRAPHS

  1. Open Access Kent State
  2. Conferences & Events
  3. Undergraduate Research Symposium
  4. 2016 - Kent State University Undergraduate Symposium on Research, Scholarship and Creative Activity
  5. Kent State University Undergraduate Symposium on Research, Scholarship and Creative Activity
  6. PHYSICAL DNA MAPPING AND PROPER INTERVAL GRAPHS
Author(s)
  • Emil Shirima
Abstract

In order to study a genome, several copies of it are cut or broken down, and some of the resulting shorter segments (called clones) are preserved for further analysis. Depending on the technique used, the preserved clones may have variable length, or they may all have essentially the same length. In the process of producing the clones, all information on their relative position along the DNA chain is lost. The goal of physical mapping of DNA is to reconstruct that order, based on experimental data on the overlaps between pairs of clones.

From the commencement of the semester, I have managed to implement a Proper Interval Graph class using Java to mimic the DNA chain. The vertices of this graph represent the clones and edges correspond to the overlapping pairs of clones.

With the graph implemented, I went on to implementing the 3-sweep LexBFS algorithm which recognizes proper interval graphs and helps in the restoration of correct interval orders. From this ordering, I am able to locate any missing edges between two vertices and even suggest possible edges between vertices which were detected as being faulty.

Currently, Dr. Dragan and I are running multiple experiments on the algorithm to better understand its behavior when certain scenarios arise.

Format
Conference Proceeding
Publication Date
2016-03-15
Contributor(s)
Faculty Mentor
Dr. Feodor Dragan
Subject
  • Theory and Algorithms
Modified Abstract

In order to study a genome, several copies of it are cut or broken down, and some of the resulting shorter segments (called clones) are preserved for further analysis. Depending on the technique used, the preserved clones may have variable length, or they may all have essentially the same length. In the process of producing the clones, all information on their relative position along the DNA chain is lost. The goal of physical mapping of DNA is to reconstruct that order, based on experimental data on the overlaps between pairs of clones.

  • Facebook
  • Linkedin
  • Twitter
  • Pinterest
  • Email
Open Access Kent State
University Libraries

Street Address

1125 Risman Dr.
Kent, OH 44242

Mailing Address

P.O. Box 5190
Kent, OH 44242-0001

Contact Us

  • oaks [at] kent [dot] edu

Quick Links

  • About
  • Frequently Asked Questions
  • Rights and Reuse

Information

  • Accessibility
  • Annual Security Reports
  • Emergency Information
  • For Our Alumni
  • For the Media
  • Health Services
  • Jobs & Employment
  • May 4th, 50th Commemoration
  • Privacy Statement
  • Website Feedback
Kent State University Home
© 2021 Kent State University All rights reserved.