Guest Editors' Introduction to the Special Section on Bioinformatics Research and Applications

THIS special section includes a selection of papers presented at the Eighth International Symposium on Bioinformatics Research and Application (ISBRA), which was held in Dallas, Texas, on 21-23 May 2012. 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 2012, 66 papers were submitted in response to the call for papers, out of which 26 papers appeared in the ISBRA proceedings published as volume 7292 of Springer Verlag’s Lecture Notes in Bioinformatics series. Extended versions of nine symposium papers were invited and accepted for publication in this special section following a rigorous review process. The selected papers cover a broad range of bioinformatics topics, including biological networks, computational complexity of problems in structural biology and genomics, and phylogenetic inference and analysis. Below, we briefly introduce each of them. The first paper by Xi Chen, Jianhua Xuan, Chen Wang,  Rebecca B. Riggins, and Robert Clarke describes a stability-based network component analysis (sNCA) to uncover regulatory networks by integrating gene expression data and binding motif information. The proposed sNCA approach overcomes a major limitation in many existing methods as caused by the inconsistency between gene expression data and TF-gene binding information. Experimental results on simulated and biological data show that sNCA achieves an improved and robust performance in TF identification as compared to the previously published NCA method and can help identify biologically meaningful regulatory networks associated with the development and progression of breast cancer. In the second paper, Matteo Re and Giorgio Valentini address an important problem in medical informatics, namely, identifying novel effects of existing therapeutic drugs by integrating heterogeneous types of network data on drug structure and effects. The authors explore various strategies for integrating such heterogeneous networks into a unified model and propose a novel scheme based on kernelized scoring functions for measuring similarity in these networks. Extensive cross-validation experiments are conducted on a data set of more than 1,200 FDA approved drugs to assess the effectiveness of various network integration approaches and scoring functions. The protein chain pair simplification problem (CPS-3F) was proposed in 2008 to simultaneously simplify both chains with respect to each other under the discrete Fréchet distance. It is unknown whether CPS-3F is NP-complete. In the third paper of the special section, Timothy Wylie and Binhai Zhu define a constrained CPS-3F problem (CPS-3F+), and prove that it is polynomially solvable by presenting a dynamic programming solution. The authors also compare the CPS3F+ solutions with previous empirical results and demonstrate some of the benefits of the simplified comparisons. In the fourth paper, Laurent Bulteau and Minghui Jiang explore the approximation complexity (1, 2)-exemplar distance between genomes. Computing this distance from a genome without duplicate genes to the genome with at most one duplicate for each gene requires keeping just one copy of each gene in the second genome so as to minimize the distance between the two reduced genomes according to some measure. It is shown that this problem is hard to approximate for popular genome rearrangement measures (such as breakpoint distance, signed reversals, and signed double-cut-and-joins) and edit distance measures (such as Levenshtein and Hamming distances). They notice that no constant-factor approximation is known for any of these measures. The fifth paper by Daniele Catanzaro, Martine Labbé, and Bjarni Halldórsson addresses the Parsimonious Loss of Heterozygosity Problem (PLOHP), which seeks to detect deletion polymorphisms based on unexpected patterns of loss of heterozygosity in a population. More specifically, PLOHP asks for partitioning putative polymorphisms of a set of individuals into the minimum number of deletion areas. The inferred deletion areas could provide fundamental insights for the development of new diagnostics and treatments. The paper presents a generalized PLOHP formulation which incorporates different recombination models and prior knowledge about the locations of deletions and reduces it to the clique partition problem in undirected catch-point interval graphs. Although the problem is shown to be NP-hard, a proposed integer programming formulation can exactly solve real instances in practical time. The last four papers address problems in evolutionary biology. The paper by Yann Christinat and Bernard Moret is