Tuyển tập báo cáo các nghiên cứu khoa học quốc tế ngành hóa học dành cho các bạn yêu hóa học tham khảo đề tài: Research Article Algorithms for Finding Small Attractors in Boolean Networks | Hindawi Publishing Corporation EURASIP Journal on Bioinformatics and Systems Biology Volume 2007 Article ID 20180 13 pages doi 2007 20180 Research Article Algorithms for Finding Small Attractors in Boolean Networks Shu-Qin Zhang 1 Morihiro Hayashida 2 Tatsuya Akutsu 2 Wai-Ki Ching 1 and Michael K. Ng3 1 Advanced Modeling and Applied Computing Laboratory Department of Mathematics The University of Hong Kong Pokfulam Road Hong Kong 2 Bioinformatics Center Institute for Chemical Research Kyoto University Uji Kyoto 611-0011 Japan 3 Department of Mathematics Hong Kong Baptist University Kowloon Tong Hong Kong Received 29 June 2006 Revised 24 November 2006 Accepted 13 February 2007 Recommended by Edward R. Dougherty A Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some ofthe proposed algorithms. For instance it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in 0 time for K 2 which is much faster than the naive 0 2 time algorithm where n is the number of genes and K is the maximum indegree. We performed extensive computational experiments on these algorithms which resulted in good agreement with theoretical results. In contrast we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard. Copyright 2007 Shu-Qin Zhang et al. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use distribution and reproduction in any medium provided the original work is properly cited. 1. INTRODUCTION The advent of DNA microarrays and oligonucleotide chips has significantly sped up the systematic study of gene interactions 1-4 . Based on .
