Unveiling disease-associated microbial biomarkers is crucial for disease diagnosis and therapy. However, the heterogeneity, high dimensionality, and large amounts of microbial data bring tremendous challenges for fundamental characteristics discovery. We present IDAM, a novel method for disease-associated biomarker inference from metagenomic and metatranscriptomic data, without requiring prior metadata. It integrates gene context conservation (uber-operon) and regulatory mechanism (gene co-expression patterns) through a mathematical graph model. We applied IDAM to inflammatory bowel disease, melanoma, Type 1 diabetes mellitus, and irritable bowel syndrome associated datasets, and demonstrated its superior performance in biomarker inference. IDAM is freely available at https://github.com/OSU-BMBL/IDAM.