A Grammatical Approach to the Alignment of Structure-Annotated Strings(Automata and Formal Language Theory)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 一般社団法人電子情報通信学会の論文
- 2005-12-01
著者
-
Kobayashi Satoshi
Department of Aging Medicine and Geriatrics, Shinshu University, Graduate School of Medicine
-
Kobayashi Satoshi
Department Of Computer Science University Of Electro-communications
-
SEKI Shinnosuke
Department of Computer Science, University of Electro-Communications
-
Seki Shinnosuke
Department Of Computer Science University Of Electro-communications
関連論文
- Spontaneous Remission of Diabetes Insipidus Due to CNS Sarcoidosis
- Organic Light-Emitting Diodes with a Nanostructured Fullerene Layer at the Interface between Alq_3 and TPD Layers
- Adenocarcinoid of the Appendix : Report of Two Cases
- Algorithms for Finding the Largest Subtree whose Copies Cover All the Leaves
- Experimental and Analytical Characterization of β-Tricalcium Phosphate Particle Reinforced Poly-L-Lactide Composites(Macro-, Micro-, Meso-, and Nano-scopic Strength of Materials Relating to Microstructures)
- Dependence of Energy Gap on x in CuAl_xGa_S_2 Mixed Crystal System : Semiconductors and Semiconductor Devices
- Absorption Edge Studies of CuGaS_2 Single Crystal
- Selective induction hyperthermia following transcatheter arterial embolization with a mixture of nano-sized magnetic particles (ferucarbotran) and embolic materials : feasibility study in rabbits
- Imaging of multistep human hepatocarcinogenesis
- Prevention of Hepatic Infarction as Acute-phase Complication of TIPS by Temporary Balloon Occlusion in a Patient with Primary Myelofibrosis
- CT Arteriographic Confirmation of Focal Hepatic Fatty Infiltration Adjacent to the Falciform Ligament Associated with Drainage of Inferior Vein of Sappey: A Case Report
- Ionic Conduction and Photoisomerization in Azobenzene Langmuir-Blodgett Films Adsorbing Cyanine Dyes
- A Patient with Advanced Hepatocellular Carcinoma Treated with Sorafenib Tosylate Showed Massive Tumor Lysis with Avoidance of Tumor Lysis syndrome
- Dependence of Absorption in Electrochromic V_2O_5 Thin Films on Crystallinity
- The Green Broad Band Photoluminescence in Sulfur Annealed CuGaS_2 Single Crystals
- Regeneration of Hemisectioned Spinal Cords With and Without Supporting Materials
- DC Green Electroluminescence of Al-CuGaS_2 Diode
- Green Eleclroluminescence from ZnS-CuGaS_2 Heterojunction Diode in DC Operation
- Preparation of Porous Polymers by "in Situ Precipitation" Using Low Molecular Weight Gelators
- Preparation of Fibrous TiO_2 Material Using an Organogelator
- New Ionic Conducting Polymer Composite Films Based on Partially Phosphorylated Poly(vinyl alcohol)and Poly(acrylic acid)
- Preparation of TiO_2 Fiber in a Sol-Gel System Containing Organogelator
- モクズガニの未成体期における鉗脚の相対成長
- モクズガニの河川における個体群構造--成熟サイズの連続的変異
- Malignant Transformation of an Intracranial Large Epidermoid Cyst With Leptomeningeal Carcinomatosis : Case Report
- Characterization of nonlinear behavior of carbon/epoxy unidirectional and angle-ply laminates
- AE Monitoring of Microdamages in Bioceramics for Artificial Joints under Simulated Body Environment(Recent Advances in Materials and Processing [II])
- 238 AE Characterization of Fracture Behavior in Bioceramics under Simulated Body Environment
- Interventional oncology : new options for interstitial treatments and intravascular approaches : Superselective TACE using iodized oil for HCC : rationale, technique and outcome
- State and Threshold Sequence Minimization Algorithm of Linear Separation Automata
- Disruption of the SCS2 Ortholog in the Alkane-Assimilating Yeast Yarrowia lipolytica Impairs Its Growth on n-Decane, but Does Not Impair Inositol Prototrophy
- 236 Experimental Characterization of Thermal Shock Fracture Behavior in Ceramic Materials
- Stochastic Regular Approximation of Tree Grammars and Its Application to Faster ncRNA Family Annotation
- Malignant pheochromocytoma of the urinary bladder : Effectiveness of radiotherapy in conjunction with chemotherapy
- The Effects of Ultrasound Stimulation on Muscle Blood Flow in the Hind Limb and Related Neural Mechanism in Anesthetized Rats
- Mechanical and Thermal Properties of Short Coir Fibre Reinforced Poly(Butylene Succinate) Biodegradable Composites
- Oxidation behavior and strength degradation of CVD-SiC coated C/C composites at high temperature in air
- Theory of Minimizing Linear Separation Automata
- Maturation and Oviposition in the Japanese Mitten Crab Eriocheir japonicus (De Haan) in Relation to Their Downstream Migration
- AE Characterization of Fracture Behavior in Bioceramics under Simulated Body Environment
- Growth of CuInS_2 Crystals by Horizontal Bridgman Method
- Incidence of Limb Loss and Bald Chelipeds in the Japanese Mitten Crab Eriocheir japonica (de Haan) in its Marine Phase
- Some Properties of Cu-Doped ZnTe Thin Films
- Organic Light-Emitting Diodes with a Nanostructured Fullerene Layer at the Interface between Alq3 and TPD Layers
- Severe Inflammation in the Background Liver Cirrhosis Correlates with the Development of Poorly Differentiated HCC in HCV-Associated Liver Cirrhosis
- Pulmonary veno-occlusive disease following reduced-intensity allogeneic bone marrow transplantation for acute myeloid leukemia
- Ionic Conduction and Photoisomerization in Azobenzene Langmuir-Blodgett Films Adsorbing Cyanine Dyes
- A Grammatical Approach to the Alignment of Structure-Annotated Strings(Automata and Formal Language Theory)
- Hydrogenated Carbon Nitride Thin Films Deposited by the Plasma Chemical Vapor Deposition Technique Using Trimethylamine and Ammonia
- Identifying Strategies Using Decision Lists from Trace Information
- Optical Properties near the Fundamental Edge of an AgGaS2 Single Crystal
- Stochastic Regular Approximation of Tree Grammars and Its Application to Faster ncRNA Family Annotation
- Stochastic Regular Approximation of Tree Grammars and Its Application to Faster ncRNA Family Annotation