Abstract
This special section consists of a selection of papers presented at the Ninth International Symposium on Bioinformatics Research and Applications (ISBRA 2013), which was held at the University of North Carolina at Charlotte, Charlotte, NC, on May 20–22, 2013. The ISBRA symposium provides a forum for the exchange of ideas and results among researchers, developers, and practitioners working on all aspects of Bioinformatics and computational biology and their applications. In 2013, 104 papers were submitted to the conference, including 46 regular submissions (up to 12 pages) and 58 short abstracts (up to four pages), among which 25 papers appeared in the ISBRA proceeding published as volume 7875 of Springer Verlag's Lecture Notes in the Bioinformatics series.
A small number of authors were invited to submit extended versions of their symposium papers to this special section. Following a rigorous review process, four papers were selected for publication. A broad range of Bioinformatics topics have been covered by this special section, including biological networks partition method, semantic similarity of Gene Ontology (GO) terms measurement, incomplete lineage sorting (ILS) method, and protein complexes detection model.
“Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage” by Falk Hüffner, Christian Komusiewicz, Adrian Liebtrau, and Rolf Niedermeier introduces a combinatorial optimization problem, the HIGHLY CONNECTED DELETION problem. The goal of this optimization problem is to remove as few edges as possible from a graph such that the remaining graph has highly connected components. The authors first demonstrate that HIGHLY CONNECTED DELETION is NP-hard even on four-regular graphs. Subsequently, both exact and heuristic approaches are proposed based on the polynomial time data reduction rules and integer linear programming with column generation.
“Measure the Semantic Similarity of GO Terms Using Aggregate Information Content” by Xuebo Song, Lin Li, Pradip K. Srimani, Philip S. Yu, and James Z. Wang proposes a novel method for the semantic similarity of GO terms measurement. Nowadays, more and more diverse biomedical dataset is annotated by GO terms. With such rapid development of GO, it is very challenging to compute functional or structural similarity of biomedical entities. Song et al. propose a similarity measurement method considering the aggregate information content of all ancestor terms in a graph for each GO term. Note that, aggregate information content not only can implicitly reflect the GO term's location, but also can represent how human being use this GO term. Experimental results indicate that the proposed method outperforms other state-of-the-art methods in terms of correlation with gene expression data.
“Effect of Incomplete Lineage Sorting On Tree-Reconciliation-Based Inference of Gene Duplication” by Yu Zheng and Louxin Zhang analyzes the effect of ILS on gene duplication inference in a species. ILS incurs larger stochastic variation in the topology of a gene tree and it likely introduces false duplication events when a tree reconciliation method is used. The authors investigate the relationship between the effect of ILS on duplication inference in a species tree and its topological parameters. The results indicate the ILS-induced bias should be considered cautiously when gene duplication is inferred via tree reconciliation.
“Detecting Protein Complexes Based on Uncertain Graph Model” by Bihai Zhao, Jianxin Wang, Min Li, Fang-Xiang Wu, and Yi Pan proposes a protein complexes detection algorithm for protein-protein interaction (PPI), called detecting complex based on uncertain graph model (DCU). To access the reliability of high-throughput protein interactions, many computational approaches based on unrealistic graph model, deterministic graphs, have been proposed. This paper intends to investigate the protein complexes detection problem in a more realistic uncertain graph model. The authors propose DCU to predict complexes from a PPI network. The experimental results demonstrate the DCU algorithm outperforms many prior computational methods.
We would like to thank the Program Committee members and external reviewers for volunteering their time to review and discuss symposium papers. We would like to extend special thanks to the Steering and General Chairs of the symposium for their leadership, and to the Finance, Publication, Publicity, and Local Organization Chairs for their hard work in making ISBRA 2013 a successful event. Furthermore, we would like to thank the Editor-in-Chief, Dr. Ying Xu and Associate Editor-in-Chief, Dr. Dong Xu for providing us with the opportunity to showcase some of the exciting research presented at ISBRA 2013 in the IEEE/ACM Transactions on Computational Biology and Bioinformatics . Last but not the least, we would like to thank all the ISBRA 2013 authors. The symposium could not continue to thrive without their high quality contributions.


