Recently, Bayesian statistical thinking has been considered as a revolutionary force within genetics and bioinformatics. Novel computational algorithms have enabled use of probability models of unprecedented degree of complexity in many applications. Pattern recognition within bioinformatics is a multifaceted field which poses an enormous challenge for the Bayesian approach to data analysis. Advantages of this framework have been demonstrated for, e.g., de novo identification of gene regulatory binding motifs, identification of gene regulatory networks, and unsupervised classification of molecular marker data. However, as complexity of data sets in bioinformatics is continuously increasing, it is likely that the conventional approaches to Bayesian computation will not yield feasible solutions in the future. Even currently, many large-scale problems are analyzed using traditional algorithmic solutions due to the exhaustive human and computing resources required by the Bayesian methods. The generic benefits of solid Bayesian modelling have been clearly demonstrated in the theoretical literature. Therefore, it would be ideal if the Bayesian modelling and computational strategies would rapidly evolve, to meet the demand from the users of extensively increasing amount of molecular information. Here we discuss potential courses for such an evolution, which could help to really revolutionize statistical thinking in pattern recognition within bioinformatics.