The significance of miRNAs has been clarified over the last decade as thousands of these small non-coding RNAs have been found in a wide variety of species. By binding to specific target mRNAs, miRNAs act as negative regulators of gene expression in many different biological processes. Computational approaches for discovery of miRNAs in genomes usually take the form of an algorithm that scans sequences for miRNA-characteristic hairpins, followed by classification of those hairpins as miRNAs or nonmiRNAs. In this study, two new approaches to genome-scale miRNA discovery are presented and evaluated. These methods, one ensemble-based and one using logistic regression, have been designed to detect miRNA candidates without relying on conservation or transcriptome data, and to achieve high-confidence predictions in reasonable computational time. GenoScan achieves high accuracy with a good balance between sensitivity and specificity. In a benchmark evaluation including 15 previously published methods, the regression-based approach in GenoScan achieved the highest classification accuracy.