In On the Origin of Species, Charles Darwin described the evolutionary relationships between organisms as branches on a tree, a diagrammatic representation of all species that have ever existed connected by common descent.
The affinities of all the beings of the same class have sometimes been represented by a great tree. I believe this simile largely speaks the truth. The green and budding twigs may represent existing species; and those produced during each former year may represent the long succession of extinct species.
— Charles Darwin, in On the Origin of Species
The metaphor has served biologists well, but reconstructing the tree of life’s many limbs, branches and twigs has not been straightforward. Evolutionary relationships between organisms thought to be true for decades have been overturned as new techniques using molecular biology coupled with computer science have been developed.
One such method — Deep Learning for Unsupervised Clustering of DNA Sequences, or DeLUCS for short — pioneered by Cheriton School of Computer Science Professor Lila Kari, her PhD students Pablo Millán Arias and Fatemeh Alipour, and her colleague Professor Kathleen Hill at Western University’s Department of Biology uses unsupervised machine learning to determine taxonomic relationships between organisms.
L to R: PhD student Fatemeh Alipour, Professor Lila Kari and PhD student Pablo Millán Arias. Professor Kathleen Hill from Western University was unavailable for the photo.
Fatemeh’s research interests are in DNA sequence classification using alignment-free methods with applications for virus–host co-evolution. Pablo Millán Arias’s research interests span DNA classification to computer vision and image pattern recognition to theoretical computer science. Lila Kari is a Professor and University Research Chair in the Cheriton School of Computer Science. Author of more than 200 peer-reviewed articles, she is regarded as one of the world’s experts in biomolecular computation — using biological, chemical and other natural systems to perform computations.
“The evolutionary relationships that DeLUCS determines match true taxonomic groups with very high accuracy, ranging from 77 per cent right up to 100 per cent across a range of genetic datasets from organisms as diverse as vertebrates, bacteria and viruses,” Professor Kari said.
But before the computational method that DeLUCS uses to determine relationships can be understood, the structure of DNA and how genomic data is processed by computers needs to be described.
DNA is a molecule inside cells that contains the genetic information for the development and functioning of an organism. DNA is a double-helix polymer, a long spiral molecule consisting of two DNA strands wound around each other. Each strand has a backbone made of alternating sugar molecules called deoxyribose and phosphate groups. Attached to this backbone are sequences of four bases — molecules known as adenine (A), cytosine (C), guanine (G) or thymine (T). The sequence of these bases along the backbone encodes information, the instructions the cell uses to make protein molecules that carry out the functions of life.
DNA is a double-helix molecule formed by base pairs (adenine and thymine depicted in blue, guanine and cytosine depicted in orange) attached to a sugar-phosphate backbone (in grey).
One way to represent the one-dimensional sequence of bases in DNA graphically is to plot them using a technique known as chaos game representation or CGR.
“The idea of CGR is to represent a DNA sequence as an image,” Professor Kari explains. “You start with a unit square with the corners labelled by the four bases: C G A T. The first pixel in the image is in the centre. The DNA sequence is read from left to right, and for each base that is read a new pixel is plotted halfway on the segment determined by the current pixel and the corner labelled by the next DNA letter being read.”
How chaos game representation (CGR) transforms a linear sequence of adenine (A), cytosine (C), thymine (T), and guanine (G) bases in DNA into a graphic pattern. This example shows the short sequence ACTCG being plotted (image on left), which results in a pattern (image on right) that a computer can process.
A dot is plotted at the centre of the square (1). Then a line is drawn from the centre dot to the corner that corresponds to the first nucleotide (A in this example) in the DNA sequence. A new dot is then plotted at the midpoint of that line (2). Then a line is drawn from that dot to the corner corresponding to the next nucleotide (C) in the sequence. The next dot is placed at the midpoint of that line (3). The process is continued until all six nucleotides (ACTCG) have been plotted, resulting in the simple graphic image on the right.
“If you do this for longer, real-life DNA sequences, you find interesting patterns,” Professor Kari continued. “But, more importantly, it turns out that genomic CGRs are species specific. In other words, CGR patterns from the same species look similar and patterns from different species look different, and the differences between the patterns are proportional to how different the species are genetically and hence evolutionarily. Interestingly, the pattern is preserved regardless of the length and the location of the subsequence sampled, provided you sample a sequence of at least 5,000 base pairs. For these reasons, CGR qualifies as a genomic signature — a quantitative value that is similar for genomes from the same species.”
A CGR representation (left) of the complete mitochondrial genome of the monarch butterfly (Danaus plexippus) (right), a familiar North American butterfly and iconic pollinator species.
To compare genomes of organisms, Professor Kari and her team used a quantized version of CGR called frequency CGR. It is similar to a CGR representation of a genome, but FCGR includes even more information from an organism’s genome — the frequency of k-mers in the DNA sequences, in other words, various substrings of nucleotides of length k in a given DNA sequence. With this k-mer information you know how many times a particular nucleotide sequence, say ACTCG, occurs in a genome. The FCGRk of a DNA sequence is a two-dimensional unit square CGR image, with the intensity of each pixel representing the frequency of a particular k-mer in the sequence.
“DeLUCS is an unsupervised machine learning technique,” Professor Kari said. “In a supervised machine learning scenario, you teach the algorithm by giving it a huge training set of labelled data — in simple terms, you tell the algorithm this is a monkey, this is an elephant, this is a dog, and so on. After you train the model, you give it new data and ask it to determine what it is. In unsupervised learning, we give the algorithm nothing — just the blind FCGR matrices — from which it finds patterns that can be used to create clusters. This method has an accuracy of almost 80 per cent and often much better.”
In their approach, FCGR pairs of sequences and of their mimics are generated and used as input to an artificial neural network.
“The initial idea came from computer vision and we adapted it for DNA sequences,” Professor Kari said. “We take a sequence and we don’t know what it is. We don’t know what cluster it belongs to, but we want to cluster them by taxonomic groups — by genus, by family, by order, and so on. What we do is slightly perturb the DNA sequence — by about 2 per cent — by inserting, deleting and substituting nucleotides, thereby creating a new sequence, but we know for sure that this mimic belongs to the same cluster. Once we do that, batches of pairs of FCGRs — the FGCR of the DNA sequence and the FGCR of the mimic sequence — are fed as input into an artificial neural network, which uses an optimization process to learn clusters. This is the novelty of this approach. To the best of our knowledge, this is the first alignment-free method that uses deep neural networks for unsupervised clustering of unlabelled DNA sequences.”
The only information external to the DNA sequence used by DeLUCS is the requirement that all genetic sequences come from the same kind of DNA — sequences from the DNA in the nucleus of cells, the DNA in the mitochondria in eukaryotic cells, the DNA in the chloroplasts in plants cells, and so on.
“One of the reasons we used mitochondrial DNA rather than nuclear DNA to determine taxonomic groups within vertebrates is because mitochondrial DNA is short enough that we can use all of it,” Professor Kari explains. “We eliminate all kinds of design decisions by sticking to mitochondrial DNA. But another advantage of using mitochondrial DNA is that you can often also look at extinct species. If you extract nuclear DNA from the tooth or bone of a Neanderthal specimen, the nuclear genome is too long to be intact, but the mitochondrial DNA is short enough that you might have the full sequence available.”
Professor Kari says that along with determining evolutionary relationships between extinct and extant species, information essential for reconstructing the tree of life, knowing evolutionary relationships has many other practical benefits.
“If we can classify bacteria quickly into strains that are antibiotic resistant versus not this information would be very useful therapeutically,” she says. “It would also be extremely useful if we can quickly detect whether a new COVID strain has evolved or if a novel virus is closely related to one known to be highly infectious and deadly.”
But there’s another pressing reason.
“We are in the midst of a global mass extinction event,” Professor Kari said. “Hundreds of species disappear every week and we cannot protect what we don’t know is disappearing. We can’t fix everything at once, but we may be able to save species most at risk of extinction. Perhaps DeLUCS can help us identify them so we can direct resources and purposeful action where they are most needed.”
To learn more about the research on which this feature is based, please see Pablo Millán Arias, Fatemeh Alipour, Kathleen A. Hill, Lila Kari. (2022) DeLUCS: Deep learning for unsupervised clustering of DNA sequences. PLoS ONE 17(1): e0261531.
