Emerging patterns, RNA structures, and routing in rings
顯現模式, RNA 結構, 及環上的路線選取
Student thesis: Doctoral Thesis
Author(s)
Related Research Unit(s)
Detail(s)
Awarding Institution | |
---|---|
Supervisors/Advisors |
|
Award date | 3 Oct 2005 |
Link(s)
Permanent Link | https://scholars.cityu.edu.hk/en/theses/theses(96116828-1465-4f31-afc8-b21d33daa9de).html |
---|---|
Other link(s) | Links |
Abstract
In this dissertation, we study the complexity of finding emerging patterns, exact matching of RNA secondary structures, the parametric alignment of two RNA structures, and four problems of requests routing and hyperedges packing in rings. Emerging patterns have been studied as a useful type of pattern for the diagnosis and understanding of diseases based on the analysis of gene expression profiles. They are useful for capturing interactions among genes (or other biological entities), for capturing signature patterns for disease subtypes, and deriving potential disease treatment plans, etc. In Chapter 1, we study the complexity of finding emerging patterns (with the highest frequency). We first show that the problem is MAX SNP-hard. This implies that polynomial time approximation schemes do not exist for the problem unless P = NP. We then prove that for any constant δ < 1, the emerging pattern problem cannot be approximated within ratio 2logδ n in polynomial time unless NP C DTIME[2polylog n], where n is the number of positions in a pattern. Many RNA structures are assembled from a collection of RNA motifs, which appear repeatedly and in various combinations. Identification of RNA structural motifs will enhance our understanding of RNA structures and functions. Search ing for secondary structural patterns in sequence databases is a basic technique and fundamental problem for extracting and identifying such motifs. A number of algorithms and programs have been developed for this purpose. We adopt a representation of secondary structure called secondary expressions, and present two algorithms for finding all exact matches of a given secondary expression. Alignment of RNA structures is a very important topic in biological research. We propose the maximization version of alignment between RNA structures. Similar to pair-wise sequence alignment, there is often disagreement about how to weight matches, mismatches, indels, and gaps when we compare two RNA structures. We develop a parametric tool, ParaRNA, for aligning two RNA structures. With this tool, the users can see explicitly and completely the effect of parameter choices on the optimal alignments of RNA structures. ParaRNA is available at http://www.cs.cityu.edu.hk/˜ lwang/software/ParaRNA. In optical communication networks, a difficult problem is how to route a set of requests as paths in a ring such that the total profits of the paths are maximized. The problem is referred to as Maximum Profits in a Ring (MPR). In Chapter 5, we give a ratio-2 approximation algorithm to the MPR problem. We also give a ratio- 2 approximation algorithm to its directed version. A more general version of the MPR problem is the Maximum Profits Hypergraph Packing in a Ring (MPHPCR) problem. The difference is to pack a set of hyperedges as paths in a cycle. We get a ratio-2 approximation algorithm for the MPHPCR problem. For one of its special versions we get a better ratio.
- Computer algorithms