Bar-coded multiplexed sequencing approaches based on new-generation sequencing technologies provide capacity to sequence a mapping population in a single sequencing run. However, such approaches usually generate low-coverage and error-prone sequences for each line in a population. Thus, it is a significant challenge to genotype individual lines in a population for linkage map construction based on low-coverage sequences without the availability of high-quality genotype data of the parental lines. In this paper, we report a method for constructing ultrahigh-density linkage maps composed of high-quality single-nucleotide polymorphisms (SNPs) based on low-coverage sequences of recombinant inbred lines. First, all potential SNPs were identified to obtain drafts of parental genotypes using a maximum parsimonious inference of recombination, making maximum use of SNP information found in the entire population. Second, high-quality SNPs were identified by filtering out low-quality ones by permutations involving resampling of windows of SNPs followed by Bayesian inference. Third, lines in the mapping population were genotyped using the high-quality SNPs assisted by a hidden Markov model. With 0.05x genome sequence per line, an ultrahigh-density linkage map composed of bins of high-quality SNPs using 238 recombinant inbred lines derived from a cross between two rice varieties was constructed. Using this map, a quantitative trait locus for grain width (GW5) was localized to its presumed genomic region in a bin of 200 kb, confirming the accuracy and quality of the map. This method is generally applicable in genetic map construction with low-coverage sequence data.