Tree structured data often appear in bioinformatics. For example, glycans, RNA secondary structures and phylogenetic trees usually have tree structures. Comparison of trees is one of fundamental tasks in analysis of these data. Various distance measures have been proposed and utilized for comparison of trees, among which extensive studies have been done on tree edit distance. In this paper, we review key results and our recent results on the tree edit distance problem and related problems. In particular, we review polynomial time exact algorithms and more efficient approximation algorithms for the edit distance problem for ordered trees, and approximation algorithms for the largest common sub-tree problem for unordered trees. We also review applications of tree edit distance and its variants to bioinformatics with focusing on comparison of glycan structures.

Active Shape Model (ASM) is a powerful statistical tool for image interpretation, especially in face alignment. In the standard ASM, local appearances are described by intensity profiles, and the model parameter estimation is based on the assumption that the profiles follow a Gaussian distribution. It suffers from variations of poses, illumination, expressions and obstacles. In this paper, an improved ASM framework, GentleBoost based SIFT-ASM is proposed. Local appearances of landmarks are originally represented by SIFT (Scale-Invariant Feature Transform) descriptors, which are gradient orientation histograms based representations of image neighborhood. They can provide more robust and accurate guidance for search than grey-level profiles. Moreover, GentleBoost classifiers are applied to model and search the SIFT features instead of the unnecessary assumption of Gaussian distribution. Experimental results show that SIFT-ASM significantly outperforms the original ASM in aligning and localizing facial features.

We developed a new method for characterizing molecular distribution in very thin liquid crystal layer (5-40 nm) evaporated onto rubbed polyimide film used by grazing-incidence X-ray diffraction (GIXD). The diffraction peaks corresponding to intermolecular correlation perpendicular to longitudinal axis of liquid crystal molecule and the clear anisotropic distribution of liquid crystal molecules in a thin layer were successfully observed. We found that in the vicinity of the alignment film, the intermolecular spacing correlation perpendicular to longitudinal axis of the 5CB molecule was expanded by the alignment film, and that the ordering of the 5CB was not so high. As the distance from the alignment film the spacing came close to the intrinsic intermolecular spacing.

Using frictional force microscopy (FFM), the friction surface characteristics were compared between twisted nematic (TN) mode and vertical alignment (VA) mode alignment films (AFs). The friction asymmetry was detected depending on temperature conditions on TN mode AF, but not on VA mode AF. The difference between two modes was explained by leaning intermolecular repulsion caused by the pre-tilt angle uniformity and the density of side chain. No level difference according to temperature conditions appeared when the pre-tilt angle were measured after liquid crystal (LC) injection.

We investigated effect of annealing after rubbing by grazing incidence X-ray diffraction, since annealing process is performed in the actual process of liquid crystal display (LCD) fabrication. It was found that rubbed surface polymers were highly crystallized by annealing at 250 after rubbing, and that the crystallization of surface polymers by annealing occurred in the aligned polymer region induced by rubbing. Crystallization of surface polymers by annealing increasingly occurred as increasing of rubbing strength. Thus, it is considered that annealing process after rubbing should also play an important role to control liquid crystal alignment in LCD.

This paper focuses on optical integration technology and its application in optical microsensors used in biomedical fields. The integration is based on the hybrid integration approach, achieving high performance, small size and weight, and lower cost. First, we describe the key technologies used in hybrid integration, namely passive alignment technology, low temperature bonding technology, and packaging technology for realizing advanced microsensors. Then, we describe an integrated laser Doppler flowmeter that can monitor blood flow in human skin.

Recently, a data-selective method has been proposed to achieve low misalignment in affine projection algorithm (APA) by keeping the condition number of an input data matrix small. We present an improved method, and a complexity reduction algorithm for the APA with the data-selective method. Experimental results show that the proposed algorithm has lower misalignment and a lower condition number for an input data matrix than both the conventional APA and the APA with the previous data-selective method.

The authors have demonstrated the local alignment of nematic liquid crystal with local micro-grating structure fabricated by the curing of an ultraviolet curable material via a three dimensional micro-fabrication technique known as two photon excitation direct laser writing [1]. The molecular alignment of the nematic liquid crystals on the fabricated micro-grating structures was firstly investigated by the observations of a local twisted nematic region in a liquid crystal cell made of a substrate with locally fabricated micro-grating structure and a counter substrate with rubbed polyimide. The optical polarizing microscope observation of the micro-grating structures indicated that liquid crystals molecules have aligned parallel to the grooves of the micro-grating structure and that local alignment was successfully achieved. The alignment characteristics of the liquid crystals on these micro-gratings was also investigated and discussed quantitatively in details through the measurement of anchoring energy by the conventional torque balance method and the Berreman method. The azimuthal anchoring energy for the micro-grating was found to be in the order of 10-6 J/m2 and inversely proportional to the grating period.

We developed new principle of electronic paper that is one side (for 2D image) or double side (for stereoscopic 3D image) light printable rewritable matter with polarization dependent gray scale. It consists of one or two liquid crystal displays based on Optical Rewritable (ORW) technology, which is the development of rotation azo-dye photoalignment. Each ORW display uses bare plastic or polarizers as substrates. The conductor is not required, as the image is formed by rewritable states of azimuthal direction, which results in 2D pattern of the liquid crystal twist angle. Continuous grey image maintains proper performance even when the device is bent. Simple construction provides durability and low cost, thin substrates minimize parallax for 3D image. Fluorescent dye dopant of liquid crystal partly absorbs light in blue and re-emit in green specter range improving photopic reflection and enhancing color of the ORW e-paper.

In this paper, we proposed a new high-rate oblique deposition method using two sputtering sources to obtain SiO2 films for a liquid crystal alignment layer. One sputtering source that operates in a metal mode supplies Si atoms to a substrate, and the other source that operates in an oxide mode supplies oxygen radicals to a substrate. To reduce the gas pressure of a deposition chamber and make the two sputtering sources operate in different modes, the sputtering sources were separated from the deposition chamber with stainless meshes, and Ar and oxygen gases were introduced separately through the two sputtering sources, i.e., Ar gas was introduced through the Si supply source and oxygen gas was introduced through the oxygen radical source. When Ar gas of 30 sccm and oxygen gas of 4 sccm were introduced into the system, the gas pressure of the deposition chamber was maintained below 1.7 mTorr and the films deposited at an incidence angle of more than 70 showed an elongated inclined columnar structure. Under this condition, a deposition rate of 30 nm/min was realized even at an incidence angle above 70, where most of the Si atoms incident to the substrate were supplied by the Si supply source and the oxygen radical source supplied oxygen radicals and promoted the oxidation of the film.

Rubbed polyimide films have been widely used as liquid crystal alignment films for liquid crystal displays. Washing after rubbing is essential to fabricate liquid crystal displays, and should affect alignment of liquid crystal as well as rubbing. We investigated the effects of rubbing condition and soaking in acetone on polyimide films by grazing incidence X-ray diffraction. It was found that soaking in acetone promoted crystallization of surface aligned polymers, and that the crystallization by acetone was dependent on the initial polymer alignment. The larger initial crystalline phase was, the more newly crystallization occurred by soaking. It was also revealed that the crystallization by soaking in acetone was completed within 1 min.

Simulation and fabrication results on back-illuminated 4-channel photodiode (PD) array with a self-aligned micro ball lens are described. The channel pitch and diameter of each photosensitive area are 250 µm and 40 µm, respectively. Measured photocurrent is 1.92 times larger than that without a lens. Alignment tolerance between the single mode fiber (SMF) optical axis and the photodiode is improved from 21.2 µm to 42.7 µm. Moreover, the separation tolerance between the fiber and the lens is 210.5 µm. These large tolerances agree with simulation results, demonstrating that the device configuration is suitable for receivers for multi-channel inter-connection. Frequency response and inter-channel cross talk are also discussed.

The optimal alignment of two given biosequences is mathematically optimal, but it may not be a biologically optimal one. To investigate more possible alignments with biological meaning, one can relax the scoring functions to get near-optimal alignments. Though the near optimal alignments increase the possibility of finding the correct alignment, they may confuse the biologists because the size of candidates is large. In this paper, we present the filter scheme for the near-optimal alignments. An easy method for tracing the near-optimal alignments and an algorithm for filtering those alignments are proposed. The time complexity of our algorithm is O(dmn) in the worst case, where d is the maximum distance between the near-optimal alignments and the optimal alignment, and m and n are the lengths of the input sequences, respectively.

Multiple sequence alignment problems in computational biology have been focused recently because of the rapid growth of sequence databases. By computing alignment, we can understand similarity among the sequences. Many hardware systems for alignment have been proposed to date, but most of them are designed for two-dimensional alignment (alignment between two sequences) because of the complexity to calculate alignment among more than two sequences under limited hardware resources. In this paper, we describe a compact system with an off-the-shelf FPGA board and a host computer for more than three-dimensional alignment based on dynamic programming. In our approach, high performance is achieved (1) by configuring optimal circuit for each dimensional alignment, and (2) by two phase search in each dimension by reconfiguration. In order to realize multidimensional search with a common architecture, two-dimensional dynamic programming is repeated along other dimensions. With this approach, we can minimize the size of units for alignment and achieve high parallelism. Our system with one XC2V6000 enables about 300-fold speedup as compared with single Intel Pentium4 2 GHz processor for four-dimensional alignment, and 100-fold speedup for five-dimensional alignment.

Coated retarders based on liquid crystal materials are typically aligned by brushing or photo-alignment. Recently, we have managed to combine the aligning and retarder function into a single material. Alignment of the new volume photo-alignable retarder (VPR-) material is induced in the bulk upon exposure to linearly polarized light. The new alignment mechanism opens up a new dimension for the design of optical retarders, especially when combined with conventional surface alignment, which allows to induce complex tilt and twist profiles.

Rubbed polyimide films have been widely used as liquid crystal alignment films for liquid crystal displays (LCDs). We investigated the effect of rubbing on the surface molecules of polyimide films by using grazing incidence X-ray diffraction (GIXD) and reflection ellipsometry. We found that rubbing not only caused the polymer chains to align in the direction of rubbing but also to elongate near the film surface. However, the in-plane distribution of surface polymer chains of polyimide film was not found to be dependent on the rubbing conditions.

Technical terms are linguistic representations of a domain concept, and their constituents are components used to represent the concept. Technical terms are usually multi-word terms and their meanings can be inferred from their constituents. Therefore, term constituents are essential for understanding the designated meaning of technical terms. However, there are several problems in finding the correct meanings of technical terms with their term constituents. First, because a term constituent is usually a morphological unit rather than a conceptual unit in the case of Korean technical terms, we need to first identify conceptual units by chunking term constituents. Second, conceptual units are sometimes homonyms or synonyms. Moreover their meanings show domain dependency. It is therefore necessary to give information about conceptual units and their possible meanings, including homonyms, synonyms, and domain dependency, so that natural language applications can properly handle technical terms. In this paper, we propose a term constituent alignment algorithm that extracts such information from bilingual technical term pairs. Our algorithm recognizes conceptual units and their meanings by finding English term constituents and their corresponding Korean term constituents for given English-Korean term pairs. Our experimental results indicate that this method can effectively find conceptual units and their meanings with about 6% alignment error rate (AER) on manually analyzed experimental data and about 14% AER on automatically analyzed experimental data.

We have been investigating an orthogonal frequency division multiple access (OFDMA) based cellular system that is called "dynamic parameter controlled orthogonal frequency and time division multiple access (DPC-OF/TDMA)" for the development of beyond third generation (B3G) mobile communication systems. Moreover, we have already proposed a time alignment control (TAC) to compensate propagation delays that induce a multiple-access interference (MAI) in the uplink OFDMA. However, that TAC includes a large amount of computations. This means that it is quite difficult for the OFDMA systems to implement TAC into volume-limited hardware devices such as field programmable gate array (FPGA). Thus, we propose a new complexity-reduced TAC (CRTAC) in this paper. CRTAC can be implemented into such devices easily. In this paper, we show some computer simulation results, and then evaluate the error rate performances of DPC-OF/TDMA employing CRTAC. Moreover, we also show the benefit of the reasonable level of the implementation complexity made by CRTAC.

In this paper, we are concerned with a structural ambiguity problem of tree adjoining grammars (TAGs), which is an essential problem when we try to model consensus structures of given set of ribonucleic acid (RNA) secondary structures by TAGs. RNA secondary structures can be represented as strings with structural information, and TAGs have a descriptive capability of this kind of strings, what we call structure-annotated strings. Thus, we can model RNA secondary structures by TAGs. It is sufficient to use existing alignment methods for just computing the optimal alignment between RNA secondary structures. However, when we also want to model the resulting alignment by grammars, if we adopt these existing methods, then we may fail in modeling the alignment result by grammars. Therefore, it is important to introduce a new alignment method whose alignment results can be appropriately modeled by grammars. In this paper, we will propose an alignment method based on TAG's derivations each corresponding to a given RNA secondary structure. For an RNA secondary structure, there exist a number of derivations of TAGs which correspond to the structure. From the grammatical point of view, the property of TAGs drives us to the question how we should choose a derivation from these candidates in order to obtain an optimal alignment. This is the structural ambiguity problem of TAGs, which will be mainly discussed in this paper. For dealing with this problem appropriately, we will propose an edit distance between two structure-annotated strings, and then present an algorithm which computes an optimal alignment based on the edit distance.

Based on the Si CMOS process, a low operating voltage and low power light emitting device is presented. It has a power transfer efficiency of 1 to 2 orders higher than previous reports and can be used as a high efficiency photodiode. Configurations using the same structure as both the light emitter and the optical receiver, and employing a simple modulation instrument is then proposed for applications in the chip-to-chip optical alignment and the signal transmission. Only single power supply is required in the emitter-receiver circuits and is compatible with other integrated circuits made by the CMOS process.