IP Library › Granted Patent US 12,374,422
Granted Patent B2
US 12,374,422 · App. 16/811,919 · Granted Jul 29, 2025

Sequence-graph based tool for determining variation in short tandem repeat regions

Inventors: Egor Dolzhenko (San Diego, CA); Michael A. Eberle (Oceanside, CA)
Assignee: ILLUMINA, INC.
G16B20/20G06N7/01G16B5/20G16B30/10G16B40/00
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,374,422
App. No.
16/811,919
Granted
Jul 29, 2025
Kind
B2
Abstract

The disclosed embodiments concern methods, apparatus, systems and computer program products for genotyping repeat sequences such as medically significant short tandem repeats (STRs). The methods involve aligning reads to a repeat sequence represented by a sequence graph, and using the aligned reads to genotype the repeat sequence. The sequence graph is a directed graph each including at least one self-loop representing a repeat sub-sequence. In some implementations, the reads are paired end reads, and both mates of each read pair may be used to genotype the repeat sequences. Some implementations can be used to determine degenerate codon repeats. Some implementations can be used to genotype repeat sequences each including two or more repeat sub-sequences. Some implementations can be used to genotype nucleic acid sequences each including at least one repeat sub-sequence and another genetic variant such as an insertion, deletion, or substitution.

Claims (40)

1. A method, implemented using a computer comprising one or more processors and system memory, for genotyping one or more repeat sequences each including one or more repeat sub-sequences, the method comprising:

(a) collecting, using the one or more processors, sequence reads of a test sample from a database, wherein the sequence reads have a length of at least 100 base pairs;

(b) aligning, by the one or more processors, the sequence reads to a reference sequence that spans the one or more repeat sequences each represented by a sequence graph, wherein the sequence graph has a data structure of a directed graph with vertices representing nucleic acid sequences and directed edges connecting the vertices, and wherein the sequence graph comprises one or more self-loops, each self-loop representing a repeat sub-sequence, each repeat sub-sequence comprising repeats of a repeat unit of one or more nucleotides, wherein the reference sequence is at least about 2000 base pairs, and wherein the number of sequence reads aligned is at least 100; and

(c) determining, by the one or more processors, one or more genotypes for the one or more repeat sequences using the sequence reads aligned to the one or more repeat sequences.

2. The method of claim 1 , wherein a repeat sequence of the one or more repeat sequences comprises a particular repeat unit comprising at least one incompletely specified nucleotide.

3. The method of claim 2 , wherein the particular repeat unit comprises degenerate codons.

4. The method of claim 1 , wherein the one or more self-loops comprise two or more self-loops representing two or more repeat sub-sequences.

5. The method of claim 1 , wherein the sequence graph further comprises two or more alternative paths for two or more alleles.

6. The method of claim 5 , wherein the two or more alleles comprise an indel or a substitution.

7. The method of claim 5 , wherein the substitution comprises a single nucleotide variant (SNV) or a single nucleotide polymorphism (SNP).

8. The method of claim 5 , further comprising genotyping the two or more alleles using sequence reads aligned to the two or more alternative paths.

9. The method of claim 8 , wherein genotyping the two or more alleles comprises providing coverages of the two or more alternative paths to a probabilistic model to determine the probabilities of the two or more alleles.

10. The method of claim 9 , wherein the probabilistic model simulates a probability of an allele as a function of the coverage of the allele, the function being selected from a Poisson distribution, negative-binomial distribution, a binomial distribution, or a beta-binomial distribution.

11. The method of claim 1 , further comprising, aligning, before (b), the sequence reads to a reference genome to determine genomic coordinates of the sequence reads, and selecting a subset of sequence reads as the sequence reads to be aligned to the one or more repeat sequences each represented by a sequence graph.

12. The method of claim 1 , wherein aligning a sequence read to the sequence graph comprises:

finding a kmer match between the sequence read and a path of the sequence graph; and

extending the kmer match to a full alignment of nodes and edges of the sequence graph including one or more self-loops.

13. The method of claim 1 , wherein aligning a sequence read to the sequence graph comprises graph shrinking by removing low confidence ends of the alignments.

14. The method of claim 1 , wherein aligning a sequence read to the sequence graph comprises alignment merging by:

aligning subsequences of the read to a sequence graph; and

merging alignments of the subsequences to form a full alignment of the sequence read.

15. The method of claim 1 , further comprising generating the sequence graph based on locus specification comprising a locus structure of the genomic locus.

16. The method of claim 1 , wherein the sequence reads comprise paired end reads, and operation (c) comprises:

(i) identifying anchor and anchored reads in the paired end reads, wherein the anchor reads are reads aligned to or near the one or more repeat sequences, and the anchored reads are unaligned reads that are paired with the anchor reads; and

(ii) determining the one or more genotypes for the one or more repeat sequences using at least the anchored reads.

17. The method of claim 1 , wherein the one or more repeat sequences comprise a short tandem repeat (STR) sequence.

18. The method of claim 17 , wherein an expansion of the STR is associated with Fragile X syndrome, amyotrophic lateral sclerosis (ALS), Huntington's disease, Friedreich's ataxia, spinocerebellar ataxia, spino-bulbar muscular atrophy, myotonic dystrophy, Machado-Joseph disease, or dentatorubral pallidoluysian atrophy.

19. The method of claim 1 , wherein each repeat sequence of the one or more repeat sequences are at least an order of magnitude longer in length than each of the sequence reads.

20. The method of claim 1 , further comprising initially aligning the sequence reads to a reference genome to determine genomic coordinates of the sequence reads prior to aligning the sequence reads to the one or more repeat sequences in (b), wherein the reference genome includes the one or more repeat sequences.

21. The method of claim 20 , wherein the reference genome is at least one of: at least 100 times larger than each of the sequence reads, or is a reference genome corresponding to a human chromosome.

22. A system comprising:

system memory; and

one or more processors configured to:

(a) collect sequence reads of a test sample from a database, wherein the sequence reads have a length of at least 100 base pairs;

(b) align the sequence reads to a reference sequence that spans the one or more repeat sequences each represented by a sequence graph, wherein the sequence graph has a data structure of a directed graph with vertices representing nucleic acid sequences and directed edges connecting the vertices, and wherein the sequence graph comprises one or more self-loops, each self-loop representing a repeat sub-sequence, each repeat sub-sequence comprising repeats of a repeat unit of one or more nucleotides, wherein the reference sequence is at least about 2000 base pairs, and wherein the number of sequence reads aligned is at least 100; and

(c) determine one or more genotypes for the one or more repeat sequences using the sequence reads aligned to the one or more repeat sequences.

23. A computer program product comprising a non-transitory machine readable medium storing program code that, when executed by one or more processors of a computer system, causes the computer system to implement a method for genotyping a repeat sequence in a test sample comprising nucleic acids, said program code comprising:

(a) code for collecting sequence reads of a test sample from a database, wherein the sequence reads have a length of at least 100 base pairs;

(b) code for aligning the sequence reads to a reference sequence that spans the one or more repeat sequences each represented by a sequence graph, wherein the sequence graph has a data structure of a directed graph with vertices representing nucleic acid sequences and directed edges connecting the vertices, and wherein the sequence graph comprises one or more self-loops, each self-loop representing a repeat sub-sequence, each repeat sub-sequence comprising repeats of a repeat unit of one or more nucleotides, wherein the reference sequence is at least about 2000 base pairs, and wherein the number of sequence reads aligned is at least 100; and

(c) code for determining one or more genotypes for the one or more repeat sequences using the sequence reads aligned to the one or more repeat sequences.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 30, 2020
From: DOLZHENKO, EGOR; EBERLE, MICHAEL A.
To: ILLUMINA, INC.
Reel/Frame 052267/0753 →
Continuity (2)
Provisional Application 62815322 · Mar 7, 2019
Related Publication 20200286586A1 · Sep 10, 2020
References Cited (62)
US 10699801B2 · Eberle et al. · 2020 [cited by applicant]
US 20140114582A1 · Mittelman et al. · 2014 [cited by applicant]
US 20150199474A1 · Kural · 2015 [cited by applicant]
US 20170249421A1 · Eberle et al. · 2017 [cited by applicant]
US 20200335178A1 · Eberle et al. · 2020 [cited by applicant]
KR 20210138556A · 2021 [cited by applicant]
RU 2263949C2 · 2005 [cited by applicant]
RU 2016139287A · 2018 [cited by applicant]
RU 2019100495A · 2019 [cited by applicant]
WO WO2013041577 · 2013 [cited by applicant]
WO WO2013149385A1 · 2013 [cited by applicant]
WO WO2015058120A1 · 2015 [cited by applicant]
WO WO2016038220A1 · 2016 [cited by applicant]
WO WO2017070096A1 · 2017 [cited by applicant]
Xu et al. “Decompositions of Multiple Breakpoint Graphs and Rapid Exact Solutions.” Algorithms in Bioinformatics. WABI 2008. Lecture Notes in Computer Science. vol. 5251, pp. 25-37. (Year: 2008). [cited by examiner]
Li et al. “A survey of sequence alignment algorithms for next-generation sequencing.” Briefings in Bioinformatics. 2010. vol. 2(5), pp. 473-483. (Year: 2010). [cited by examiner]
Szalkowski. “Fast and robust multiple sequence alignment with phylogeny-aware gap placement.” BMC Bioinformatics. 2012. vol. 13(129), pp. 1-11. (Year: 2012). [cited by examiner]
Szalkowski et al. “Graph-based modeling of tandem repeats improves global multiple sequence alignment.” Nucleic Acids Research. 2013. vol. 41(17), pp. 1-11. (Year: 2013). [cited by examiner]
Rand et al. “Coordinates and intervals in graph-based reference genomes.” BMC Bioinformatics. 2017. vol. 18(263), pp. 1-8. (Year: 2017). [cited by examiner]
Donev et al. “Recruitment of Heterogeneous Nuclear Ribonucleoprotein A1 in Vivo to the LMP/TAP Region of the Major Histocompatibility Complex.” The Journal of Biological Chemistry. 2003. vol. 278(7), pp. 5214-5226. (Yea… [cited by examiner]
Pellegrini et al. “Tandem repeats discovery service (TReaDS) applied to finding novel cis-acting factors in repeat expansion diseases.” BMC Bioinformatics. 2012. vol. 13(Suppl 4):S3, pp. 1-15. (Year: 2012). [cited by examiner]
Treangen et al. “Repetitive DNA and next-generation sequencing: computational challenges and solutions.” Nature Reviews: Genetics. 2012. vol. 13, pp. 36-46. (Year: 2012). [cited by examiner]
Compeau et al. “How to apply de Bruijn graphs to genome assembly.” Computational Biology, vol. 29, No. 11, pp. 987-991. (Year: 2011). [cited by examiner]
Flicek et al. “Sense from sequence reads: methods for alignment and assembly.” Nature Methods Supplement, vol. 6, No. 11S, pp. S6-S12. (Year: 2009). [cited by examiner]
“Tool for Simulating Sequence Reads from a Reference Genome”, https://github.com/lh3/wgsim., 2011, 1-2. [cited by applicant]
1000 Genomes Project, Consortium, “A global reference for human genetic variation”, Nature 526, Oct. 1, 2015, 68-74. [cited by applicant]
Amiel, J., et al., “Polyalanine expansion and frameshift mutations of the paired-like homeobox gene PHOX2B in congenital central hypoventilation syndrome”, Nature Genetics 33, 2003, 459-461. [cited by applicant]
Benjamini, et al., “Summarizing and correcting the GC content bias in high-throughput sequencing”, Nucleic Acids Research, Feb. 9, 2012, 1-14. [cited by applicant]
Cornish-Bowden, A., et al., “Nomenclature for incompletely specified bases in nucleic acid sequences: recommendations 1984.”, Nucleic Acids Research 13(9), 1985, 3021-3030. [cited by applicant]
Dashnow, H., et al., “STRetch: detecting and discovering pathogenic short tandem repeat expansions”, Genome Biology 19:191, Aug. 21, 2018, 1-13. [cited by applicant]
Dilthey, A., et al., “Improved genome inference in the MHC using a population reference graph”, Nature Genetics 47, 2015, 682-688. [cited by applicant]
Doi, et al., “Rapid detection of expanded short tandem repeats in personal genomics using hybrud sequencing”, Bioinformatics vol. 30, No. 6, Mar. 15, 2014, 815-822. [cited by applicant]
Dolzhenko, E., et al., “Detection of long repeat expansions from PCR-free whole-genome sequence data”, Genome Res 27, Sep. 8, 2017, 1895-1903. [cited by applicant]
Dryland, et al., “Simple repeat-primed PCR analysis of the Myotonic Type 1 Gene in a clinical diagnostics environment”, URL:http://www.hindawi.com/journals/jnd/2013/857564. [cited by applicant]
Froggatt, N., et al., “A common MSH2 mutation in English and North American HNPCC families: Origin, phenotypic expression, and sex specific differences in colorectal cancer”, J. Med Genet 36(2), Feb. 1999, 97-102. [cited by applicant]
Garrison, E., et al., “Variation graph toolkit improves read mapping by representing genetic variation in the reference.”, Nat Biotechnol 36(9), Oct. 2018, 875-879. [cited by applicant]
Gymrek, M., et al., “Abundant contribution of short tandem repeats to gene expression variation in humans”, Nature Genetics 48, 2016, 22-29. [cited by applicant]
Hannan, A., et al., “Tandem repeats mediating genetic plasticity in health and disease.”, Nat Rev Genetics 19(5), May 2018, 286-298. [cited by applicant]
Lee, C., et al., “Multiple sequence alignment using partial order graphs”, Bioinformatics 18(3), Mar. 2002, 452-464. [cited by applicant]
Lee, J., et al., “Pathogenic Mechanisms of Myotonic Dystrophy”, Biochemical Society Transactions 37(6), Nov. 19, 2009, 1281-86. [cited by applicant]
Li, H., et al., “Aligning Sequence Reads, Clone Sequences and Assembly Contigs with BWA-MEM”, https://arxiv.org/abs/1303.3997, 2013, 1-3. [cited by applicant]
Lincoln, S., et al., “A Rigorous Interlaboratory Examination of the Need to Confirm Next-Generation Sequencing-Detected Variants with an Orthogonal Method in Clinical Genetic Testing”, The Journal of Molecular Diagnosti… [cited by applicant]
Mousavi, N., et al., “Profiling the genome-wide landscape of tandem repeat expansions”, bioRxiv 361162; doi: https://doi.org/10.1101/361162, Jul. 3, 2018, 1-25. [cited by applicant]
Paten, B., et al., “Genome graphs and the evolution of genome inference”, Genome Res, Mar. 14, 2017, 1-56. [cited by applicant]
Richards, R., “Dynamic mutations: a decade of unstable expanded repeats in human genetic disease”, Oxford Univerity Press 10(20), 2001, 2187-2194. [cited by applicant]
Shoubridge, C., et al., “Polyalanine Tract Disorders and Neurocognitive Phenotypes.”, Advances in Experimental Medicine and Biology 769, 2012, 185-203. [cited by applicant]
Tang, H., et al., “Profiling of Short-Tandem-Repeat Disease Alleles in 12,632 Human Whole Genomes”, Am J Hum Genet 101(5), Nov. 2, 2017, 700-715. [cited by applicant]
Novak, P., et al., “RepeatExplorer: a Galaxy-based web server for genome-wide characterization of eukaryotic repetitive elements from next-generation sequence reads”, Bioinformatics 29(6), Feb. 1, 2013, 792-793. [cited by applicant]
Novak, P., et al., “TAREAN: a computational tool for identification and characterization of satellite DNA from unassembled short reads”, Nucleic Acids Research 45(12) e111, Apr. 10, 2017, 1-10. [cited by applicant]
PCT/US2020/021550, “International Search Report and Written Opinion”, Jun. 3, 2020, 1-18. [cited by applicant]
RU Office Action dated Nov. 1, 2023, in Application No. RU2023116499 with English translation. [cited by applicant]
RU Office Action dated Oct. 24, 2022, in application No. RU2021108143 with English translation. [cited by applicant]
SG Office Action dated May 3, 2023, in application No. SG11202103205Q. [cited by applicant]
AU Office Action dated Jun. 3, 2022, in Application No. AU2021202149. [cited by applicant]
Cao, M.D., et al., “Inferring Short Tandem Repeat Variation From Paired-end Short Reads,” Nucleic acids research, 2014, vol. 42(3), pp. 1-11. [cited by applicant]
Extended European search report dated Oct. 21, 2022, in Application No. EP22168725.4. [cited by applicant]
International Preliminary Report on Patentability dated Mar. 23, 2017 in Application No. PCT/EP2015/070902. [cited by applicant]
U.S. Non-Final office Action dated Jan. 11, 2019 in U.S. Appl. No. 15/510,219. [cited by applicant]
U.S. Non-Final Office Action dated Nov. 15, 2023 in U.S. Appl. No. 16/869,455. [cited by applicant]
U.S. Notice of Allowance dated Feb. 10, 2020 in U.S. Appl. No. 15/510,219. [cited by applicant]
U.S. Notice of Allowance dated Jun. 5, 2020 in U.S. Appl. No. 15/510,219. [cited by applicant]
U.S. Notice of Allowance dated May 28, 2020 in U.S. Appl. No. 15/510,219. [cited by applicant]