Optimal Permutation Recovery and Estimation of Bacterial Growth Dynamics
Accurately quantifying microbial growth dynamics for species without complete genome sequences is biologically important but computationally challenging in metagenomics. Here we present DEMIC, a new multi-sample algorithm based on contigs and coverage values, to infer relative distances of contigs from replication origin and to accurately estimate and compare bacterial growth rates between samples. We demonstrate robust performances of DEMIC for a wide range of sample sizes and assembly qualities using various synthetic and real data sets. We provide theoretical analysis to explain why DEMIC works in the framework of optimal permutation recovery.