As I understand it, when we map a genome, the process is much more complicated than say copying text out of a book. The genetic sequence cannot be copied from a genetic sample in a single pass, so instead the sequence is split into many very small sub sequences called reads. These reads are then assembled into the complete genome using De Bruijn graphs. To accelerate this process, a reference genome is used to help figure out which subsequences connect to each other.

In the case of the human genome project, obviously no reference human genome existed. Was some reference genome used? If so, what was the reference genome? If not, how were they able to assemble the human genome?

Based on my reading, constructing the final assembly from a De Bruijn graph is NP-Hard. So, doing the assembly from scratch seems completely intractable. The human genome is 3,000,000,000 letters, and an individual read is about 300 letters. This means there are at least 30,000,000 subsequences, and probably many more than that given how redundant the sequencing process is. NP-hard problems tend to become completely intractable with problem sizes in the hundreds, and this problem size is in the millions if not billions. That's why it seems essential that the assembly process used some sort of reference to greatly speed things up, but some googling around hasn't identified the reference used.

  • 7
    $\begingroup$ This seems like it might be more suited to the History of Science and Mathematics site. The short answer is that the chromosomes aren't one single "string", but 23 separate strings. In addition, IIRC the problem was further simplified by doing (possibly multiple rounds of) sub-cloning. Have you tried searching for something like "history of human genome sequencing project" — I'm certain that you would find as much detail as you want. $\endgroup$
    – tyersome
    Oct 11, 2021 at 2:41
  • 3
    $\begingroup$ The technology that you are speaking about isthe next generation sequencing, which is not the one that was used in the first human genome project. Also, de novo genome assembly (e.g., with de brujin graphs) and genome mapping are different things - the former is done when the reference sequence is not available. Not sure what the OP means by bootstrapping... $\endgroup$
    – Roger V.
    Oct 11, 2021 at 5:07
  • $\begingroup$ Note that, while we have a "complete" human genome, it is not an ungapped genome. Telomere-to-telomere assembly has only been completed for the human X chromosome and chromosome 8, I believe. The unresolved gaps are caused by regions that are hard to assemble like segmental duplications, ribosomal rRNA gene arrays, and satellite arrays. These gaps can only be closed by careful long-read sequencing. $\endgroup$
    – acvill
    Oct 11, 2021 at 13:27
  • 3
    $\begingroup$ The process that you describe is true in some cases for the problem of shotgun genome assembly, but it does not describe the strategy taken by the HGP. This resource may prove helpful for understanding how a highly iterative procedure leveraging information from many disparate sources (sub-assembly, BACs, physical mapping) was used by HGP to get around the computational issues: nature.com/scitable/topicpage/… $\endgroup$ Oct 11, 2021 at 20:18


You must log in to answer this question.

Browse other questions tagged .