Dissertation > Excellent graduate degree dissertation topics show

Fast Computing Method for Genes by Reversal/Transposition

Author: ShenFei
Tutor: ZhuDaMing；ZhongJie
School: Shandong University
Course: Computer technology
Keywords: Genome Reorganization Algorithm Complexity Approximate performance ratio
CLC: TP399-C8
Type: Master's thesis
Year: 2009
Downloads: 14
Quote: 0
Read: Download Dissertation

Abstract

Genome reorganization genomic change the biochemical processes of gene order. The reorganization of the genome sequencing problem comes from the comparison of gene order in the genome. The goal is to find the shortest recombinant sequence of operations will be a genome into another genome. Genome reorganization of the sort used to infer the evolutionary process of life due to the reorganization, the genome reorganization Sort calculation helps the exact analysis of the cause of disease principle, contribute to the rapid diagnosis of disease to effectively treat the disease, help the molecular structure of the precise design of Chinese medicine, improve the efficacy of the drug. A chromosome by a gene sequence, the genome is a chromosome set. Can once genome reorganization seen as change of gene order in one operation. Assume that nature always choose the most effortless way or the fastest way to complete the evolution of life, the number of operations to restructure at least target, to calculate a genome into another reorganization operation sequence of the genome the genome reorganization evolution process. Sankoff et al earliest design a flip of the genome and the shift (Translocation) sorting algorithm (Reversal). Given that the two genomes A, B, after the predetermined operations may be used, the distance A, B between the transition from A to B is at least the number of transformation operations. Seeking transform distance and sequence of transformations between these genomic called the genome reorganization scheduling problem. Basic restructuring operation three: flip (reversal), shift (translocation) and translocation transposition. The sake of simplicity, in the discussion genome rearrangement distance, people tend to consider only one or two of operation. In this paper, using the flip and turn-bit operating signed genome sort of problem. Each genome represents a signed integer sequence, a the integer symbol indicates a gene. The genome Flip / translocation Sort asked to find a flip or a turn-bit operating sequence, given a signed integer arranged into another signed integer arranged. Gu QP gives an approximate performance ratio for polynomial time approximation algorithms, but no algorithm implementation procedures and algorithms to calculate the performance of the actual test results. This article focuses on the realization of the genome flip / transposition sort algorithm. First introduced the approximate performance ratio of the algorithm thought, and then discuss the algorithm C program and to the actual data test procedures for solving performance. The implementation of the algorithm using one-dimensional array and linked list storage integers arranged so that the sub-sequence of flips and translocation operations to be completed in constant time. In the fourth chapter, according to the actual implementation of the results of a small amount of data manually test and large amounts of data to find the approximate performance than the worst example is that all the elements are all included in the linked list in a circle and each operation can only reduce a black edge, special can be obtained in the case of the optimal solution. As innovations: (1) for the first time designed and implemented the approximate performance ratio of 2 to flip the genome / transposition sort algorithm validation algorithm for solving performance and minimum boundaries; (2) the use of the algorithm to find an instance approximation algorithm for the instance performance ratio of 2; (3) using a one-dimensional array and a linked list storage integers arranged to improve the program run faster.

Related Dissertations

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > In other aspects of the application
© 2012 www.DissertationTopic.Net Mobile