The expressed sequence tags, derived from the developing tilapia brain, were established in our laboratory. An unique gene, high mobility group proteins 2 (HMG2), were investigated. HMG2 is a non-histone chromatin protein. HMG2 cloned from tilapia, Oreochromis mossambicus, is a gene with open reading frame 642bps, and deduced as 213 amino acid protein sequence. NCBI Conserved Domain search, the Gene Ontology, NEBcutter restrict enzyme analysis, NCBI blastx, and neighbor phylogenetic tree were used for the bioinformatic analysis. In the present study, the protein expression of HMG2 in the BL21 E.coli system, a prokaryotic system, and purified with 6X His Tag NI-NTA affinity chromatography.

With the rapid advances in technologies, strategies for efficiently operating the spatial data are needed. The spatial data consists of points, lines, rectangles, regions, surface, and volumes. In this thesis, we focus on the region data. There are many important and efficient operations for the region data, such as neighbor finding, rotation, and mirroring. The nearest neighbor (NN) finding is frequently used in geographic information system (GIS). We can find the specific point (e.g., a park, a department store, etc.) that is the closest to our position in geographical information systems. In any representation for the region data, it is not instinctive and easy for nearest neighbor finding, since the coordinate information has been lost. Voros, Chen, and Chang have proposed the strategies for the nearest neighbor finding based on the quadtree in eight directions. Chen and Chang have proposed the nearest neighbor finding based on the Peano curves. These strategies for the nearest neighbor finding based on the quadtree and the Peano curve use a looping process, which is time-consuming. On the other hand, in recent years, many researchers have also focused on finding efficient strategies for the rotating and mirroring operations, which is useful when the animation is performed by computers. The boolean function-based encoding is a considerable amount of space-saving with respect to the other binary image representation. The CBLQ representation saves memory space as compared to the other binary image representations that have proposed the strategies of the set operations. However, the processes for obtaining the rotated or mirrored code based on these two representations are time-consuming, since the coordinate information of all pixels has been lost. Therefore, in this thesis, first, for the nearest neighbor finding based on the quadtrees and the Peano curve, we propose the strategy which uses the bitwise and arithmetic operations, and it is more efficient than the strategies based on the looping processes. Next, we propose efficient strategies for rotating and mirroring images based on the boolean function-based encoding and constant bit-length linear quadtrees (CBLQ) representations. From our simulation study, first, we show that our strategies based on the quadtree and the Peano curve require the least CPU-time and our strategy based on the Hilbert curve requires the least total time (the CPU-time + the I/O time) among the strategies for the nearest neighbor finding based on the quadtree and the three space-filling curves. Next, in most of cases, when the black density is no larger than 50%, the CPU-time based on the boolean function-based encoding is less than that based on CBLQ.

It has been shown that focusing the training algorithms to the decision boundary vicinity data can improve the accuracy of several classification methods. However, previous approaches for fining decision boundary vicinity data are either computationally tedious or may perform poorly in handling problems with class overlapping. With the application of the nearest neighbor rule, this work proposes a new criterion to characterize the nearness of the training samples to the decision boundary. To demonstrate the effectiveness of the proposed approach, the proposed method is integrated with a nearest neighbor classifier design method and a neural work training approach. Experimental results show that the proposed method can reduce the size and classification error for both of the tested classifiers.

With the proliferation of wireless communications and rapid advances in technologies, algorithms for efficiently answering queries about large number of spatial data are needed. Spatial data consists of spatial objects including data of higher dimension. Neighbor finding is one of the most important spatial operations in the field of spatial data structures. In recent years, many researchers have focused on finding efficient solutions to the nearest neighbor problem (NN) which involves determining the point in a data set that is the nearest to a given query point. It is frequently used in Geographical Information Systems (GIS). A block B is said to be the neighbor of another block A, if block B has the same property as block A has and covers an equal-sized neighbor of block A. Jozef Voros has proposed a neighbor finding strategy on images represented by quadtrees, in which the four equal-sized neighbors (the east, west, north, and south directions) of block A can be found. However, based on Voros's strategy, the case that the nearest neighbor occurs in the diagonal directions (the northeast, northwest, southeast, and southwest directions) will be ignored. Moreover, there is no total ordering that preserve proximity when mapping a spatial data from a higher dimensional space to a 1D-space. One way of effecting such a mapping is to utilize space-filling curves. Space-filling curves pass through every point in a space and give a one-one correspondence between the coordinate and the 1D-sequence number of the point. The Peano curve, proposed by Orenstein, which maps the 1D-coordinate of a point by simply interleaving the bits of the X and Y coordinates in the 2D-space, can be easily used in neighbor finding. But with the data ordered by the RBG curve or the Hilbert curve, the neighbor finding would be complex. The RBG curve achieves savings in random accesses on the disk for range queries and the Hilbert curve achieves the best clustering for range queries. Therefore, in this thesis, we first show the missing case in the Voros's strategy and show the ways to find it. Next, we show that the Peano curve is the best mapping function used in the nearest neighbor finding. We also show the transformation rules between the Peano curve and the other curves such that we can efficiently find the nearest neighbor, when the data is linearly ordered by the other curves. From our simulation, we show that our proposed two strategies can work correctly and faster than the conventional strategies in nearest neighbor finding. Finally, we present a revised version of NA-Trees, which can work for exact match queries and range queries from a large, dynamic index, where an exact match query means finding the specific data object in a spatial database and a range query means reporting all data objects which are located in a specific range. By large, we mean that most of the index must be stored in secondary memory. By dynamic, we mean that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand.

Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2003. / Includes bibliographical references (leaves 40-43). Also available in electronic version. Access restricted to campus users.

In Voronoi-based nearest neighbor search, the Voronoi cell of every point p in a database can be used to check whether p is the closest to some query point q. We extend the notion of Voronoi cells to support uncertain objects, whose attribute values are inexact. Particularly, we propose the Possible Voronoi cell (or PV-cell). A PV-cell of a multi-dimensional uncertain object o is a region R, such that for any point p ∈ R, o may be the nearest neighbor of p. If the PV-cells of all objects in a database S are known, they can be used to identify objects that have a chance to be the nearest neighbor of q. However, there is no efficient algorithm for computing an exact PV-cell. We hence study how to derive an axis-parallel hyper-rectangle (called the Uncertain Bounding Rectangle, or UBR) that tightly contains a PV-cell. We further develop the PV-index, a structure that stores UBRs, to evaluate probabilistic nearest neighbor queries over uncertain data. An advantage of the PV-index is that upon updates on S, it can be incrementally updated. Extensive experiments on both synthetic and real datasets are carried out to validate the performance of the PV-index. / published_or_final_version / Computer Science / Master / Master of Philosophy

In this dissertation we present deterministic algorithms for reliable and efficient communication in ad hoc networks. In the first part of this dissertation we give a specification for a reliable neighbor discovery layer for mobile ad hoc networks. We present two different algorithms that implement this layer with varying progress guarantees. In the second part of this dissertation we give an algorithm which allows nodes in a mobile wireless ad hoc network to communicate reliably and at the same time maintain local neighborhood information. In the last part of this dissertation we look at the distributed trigger counting problem in the wireless ad hoc network setting. We present a deterministic algorithm for this problem which is communication efficient in terms of the the maximum number of messages received by any processor in the system.

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2004. / Includes bibliographical references (leaves 91-95). Also available in electronic version. Access restricted to campus users.

Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2005. / Includes bibliographical references (leaves 60-61). Also available in electronic version.

We present an algorithm for c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time ofO(dn^{1/c^2+o(1)}) and space O(dn + n^{1+1/c^2+o(1)}).