On the Complexity and Completeness of Robust Biclustering Algorithm (ROBA)

摘要：

A biclustering algorithm named ROBA has been used in a number of recent works. We present a time and space efficient implementation of ROBA that reduces the time and space complexity by an order of L where L is the number of distinct values present in the data. Our implementation runs almost 11 times faster than the existing implementation on Yeast gene expression dataset. We also improve ROBA and then use it to present an iterative algorithm that can find all perfect biclusters with constant values, constant values on rows and constant values on columns. Though our algorithm may take exponential time in the worst case, we use some subtle observations to reduce computational time and space. Experimental result reveals that our algorithm runs in reasonable time on Yeast gene expression dataset and finds almost 10 times more biclusters than ROBA.

作者: Muhammad Ibrahim Nasimul Noman Hitoshi Iba

作者单位: Dept.of Computer Science and Engineering University of Dhaka, Bangladesh Dept.of Electrical Engineering and Information Systems University of Tokyo, Japan

会议类型: 国际会议

会议名称: The 4th International Conference on Bioinformatics and Biomedical Engineering(第四届IEEE生物信息与生物医学工程国际会议 iCBBE 2010)

会议地点: 成都

会议语种:英文

页码: 1-4

在线出版日期: 2010-06-18（万方平台首次上网日期，不代表论文的发表时间）