Institute of Information Science, Academia Sinica

Research Overview

Print

2008 Achievements

An Incentive-Based Fairness Mechanism for Multi-Hop Wireless Backhaul Networks with Selfish Nodes

IEEE Transactions on Wireless Communications Vol. 7, No. 2, pp. 697-704, February 2008

JengFarn Lee [1], Wanjiun Liao [2], and Meng Chang Chen [3]

Author Affiliations
  • [1] National Chung Cheng University
  • [2] National Taiwan University
  • [3] Institute of Information Science, Academia Sinica

In this paper, we study the fairness problem in multi-hop wireless backhaul networks in the presence of selfish Transit Access Points (TAPs). We design an incentive-based mechanism which encourages TAPs to forward data for other TAPs, and thus eliminates the location-dependent unfairness problem in the backhaul network. We prove the correctness and truthfulness of the proposed mechanism, and evaluate its performance via ns-2 simulations. The results show that the proposed mechanism achieves fairness even when there are idle TAPs in the network.

View Full Paper

BIOSMILE web search: a web application for annotating biomedical entities and relations

Nucleic Acids Research, 2008, Vol. 36, Web Server issue, W390–W398

Hong-Jie Dai [1,2], Chi-Hsin Huang [1], Ryan T. K. Lin [1], *Richard Tzong-Han Tsai [3], and Wen-Lian Hsu [1,2]

Author Affiliations
  • [1] Institute of Information Science, Academia Sinica
  • [2] Department of Computer Science, National Tsing-Hua University
  • [3] Department of Computer Science & Engineering, Yuan Ze University

BIOSMILE web search (BWS), a web-based NCBI-PubMed search application, which can analyze articles for selected biomedical verbs and give users relational information, such as subject, object, location, manner, time, etc. After receiving keyword query input, BWS retrieves matching PubMed abstracts and lists them along with snippets by order of relevancy to protein–protein interaction. Users can then select articles for further analysis, and BWS will find and mark up biomedical relations in the text. The analysis results can be viewed in the abstract text or in table form. To date, BWS has been field tested by over 30 biologists and questionnaires have shown that subjects are highly satisfied with its capabilities and usability. BWS is accessible free of charge at http://bioservices.cse.yzu.edu.tw/BWS .

View Full Paper

Discovering gapped binding sites of yeast transcription factors

PNAS 2008 105 (7) 2527-2532

Chien-Yu Chen [1], Huai-Kuang Tsai [2], Chen-Ming Hsu [3], Mei-Ju May Chen [4], Hao-Geng Hung [5], Grace Tzu-Wei Huang [6], and Wen-Hsiung Li [6,7]

Author Affiliations
  • [1] Department of Bio-Industrial Mechatronics Engineering
  • [2] Institute of Information Science, Academia Sinica
  • [3] Department of Computer Science and Engineering, Yuan Ze University
  • [4] Graduate Institute of Biomedical Electronics and Bioinformatics
  • [5] Department of Computer Science and Informatics Engineering, National Taiwan University
  • [6] Research Center for Biodiversity and Genomics Research Center, Academia Sinica
  • [7] Department of Ecology and Evolution, University of Chicago

A gapped transcription factor-binding site (TFBS) contains one or more highly degenerate positions. Discovering gapped motifs is difficult, because allowing highly degenerate positions in a motif greatly enlarges the search space and complicates the discovery process. Here, we propose a method for discovering TFBSs, especially gapped motifs. We use ChIP-chip data to judge the binding strength of a TF to a putative target promoter and use orthologous sequences from related species to judge the degree of evolutionary conservation of a predicted TFBS. Candidate motifs are constructed by growing compact motif blocks and by concatenating two candidate blocks, allowing 0–15 degenerate positions in between. The resultant patterns are statistically evaluated for their ability to distinguish between target and nontarget genes. Then, a position-based ranking procedure is proposed to enhance the signals of true motifs by collecting position concurrences. Empirical tests on 32 known yeast TFBSs show that the method is highly accurate in identifying gapped motifs, outperforming current methods, and it also works well on ungapped motifs. Predictions on additional 54 TFs successfully discover 11 gapped and 38 ungapped motifs supported by literature. Our method achieves high sensitivity and specificity for predicting experimentally verified TFBSs.

View Full Paper