IP Library › Granted Patent US 12,580,046
Granted Patent B2
US 12,580,046 · App. 17/651,396 · Granted Mar 17, 2026

Computer method and system of identifying genomic mutations using graph-based local assembly

Inventors: John Browning (Woburn, MA); Deniz Kural (Somerville, MA)
Assignee: Seven Bridges Genomics Inc.
G16B30/20G16B20/00G16B20/20G16B30/00G16B30/10G16B45/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,580,046
App. No.
17/651,396
Granted
Mar 17, 2026
Kind
B2
Abstract

Computer-implemented methods and systems for performing a local assembly of a genomic region of interest include the de novo or assisted creation of a directed graph, such as a directed acyclic graph (DAG), from a plurality of obtained nucleotide sequence reads. First and second sequence reads are aligned to each other to define at least one node of the DAG. Successive alignments of the remaining sequence reads to the then-defined DAG are performed to extend nodes and/or add nodes to the DAG. Graph-aware alignment techniques that produce alignment scores or indicators are employed in defining the nodes of the DAG from the sequence reads. The created DAG represents and describes in detail the genomic region of interest and can be used to perform variant calls.

Claims (78)

1 . A computer-implemented method of identifying a genomic mutation, the method comprising:

by a processor coupled to a memory area, the memory area comprising a plurality of nucleotide sequence reads mapping to a genomic region of interest:

creating in computer memory a directed graph from the plurality of nucleotide sequence reads by:

(i) aligning a first sequence read of the plurality of nucleotide sequence reads to a second sequence read of said plurality and producing an alignment indicator;

(ii) defining at least one node of the directed graph as a function of the produced alignment indicator, each defined node representing a nucleotide sequence portion;

(iii) successively, for each remaining sequence read after the first and second sequence reads, aligning the remaining sequence read against the then defined directed graph and producing a respective alignment indicator that indicates a match to an existing node of the directed graph or that extends the directed graph by lengthening a node with additional nucleotide sequences, by adding new nodes to incorporate new sequence variations, or a combination thereof, the created directed graph providing a local assembly of the sequence reads;

performing variant calls with the created directed graph and a reference genome, the performing variant calls including detecting a variant, represented in a node of the directed graph, with respect to the reference genome; and

providing an output identifying a genomic mutation based on the detected variant.

2 . The method of claim 1 , further comprising initially positioning the plurality of nucleotide sequence reads with respect to a reference sequence and sorting the plurality of nucleotide sequence reads based on the positioning of said sequence reads with respect to the reference sequence; and

wherein the successive aligning progresses in sorted order of the nucleotide sequence reads.

3 . The method of claim 1 , wherein creating the directed graph includes aligning the first sequence read to the reference sequence prior to the alignment of the second sequence read to the first sequence read.

4 . The method of claim 2 , wherein the reference sequence is a linear or graph reference genome.

5 . The method of claim 2 , further comprising performing variant calls at the initial positioning, resulting in a first set of variant calls.

6 . The method of claim 5 , wherein the genomic region of interest is determined by the first set of variant calls.

7 . The method of claim 2 , the sorting further comprising: for a paired-end sequence read that is unmapped to the reference genome, assigning a position to one of the unmapped sequence reads of a pair based on (i) position of the other sequence read of the pair, and (ii) an insert size defined as a function of an inferred length of a DNA molecule that originated the paired-end sequence read.

8 . The method of claim 1 , wherein the aligning of the first sequence read to the second sequence read accounts for gaps between the first and second sequence reads.

9 . The method of claim 1 , wherein:

the aligning of sequence reads employs a Smith-Waterman technique, a Graph-Smith-Waterman technique, or a graph-aware optimal alignment algorithm; and

the produced alignment indicator is a Compact Idiosyncratic Gapped Alignment Report (CIGAR) string.

10 . The method of claim 9 , wherein defining the nodes of the directed graph as a function of the produced CIGAR strings includes:

(i) if the CIGAR string indicates the first and second sequence reads are identical, defining a single node in the directed graph, the single node representing the corresponding identical nucleotide sequence of the first and second sequence reads;

(ii) if the CIGAR string indicates the first and second sequence reads are overlapping, defining a single node in the directed graph representing the corresponding overlapping nucleotide sequences of the first and second sequence reads and any nonoverlapping tails of the first and second sequence reads; and

(iii) if the CIGAR string indicates the first and second sequence reads are a variation of each other, defining in the directed graph respective single nodes representing sequence portions in common and respective alternative nodes representing variations.

11 . The method of claim 1 , wherein defining the nodes of the directed graph as a function of the alignment indicator includes:

(i) if the alignment indicator indicates the first and second sequence reads are identical, defining a single node in the directed graph, the single node representing the corresponding identical nucleotide sequence of the first and second sequence reads;

(ii) if the alignment indicator indicates the first and second sequence reads are overlapping, defining a single node in the directed graph representing the corresponding overlapping nucleotide sequences of the first and second sequence reads and any nonoverlapping tails of the first and second sequence reads;

(iii) if the alignment indicator indicates the first and second sequence reads are a variation of each other, defining in the directed graph respective single nodes representing sequence portions in common and respective alternative nodes representing variations.

12 . The method of claim 1 , further comprising pruning the created directed graph by removing low-confidence nodes, wherein the low-confidence nodes represent a low number of mapped sequence reads or low-quality sequence reads.

13 . The method of claim 1 , further comprising incorporating the created directed graph into a reference sequence and re-positioning the plurality of sequence reads to the updated reference sequence incorporating the created directed graph, rescuing unmapped and/or misaligned sequence reads.

14 . The method of claim 1 , wherein performing variant calls includes:

transforming at least one path through the directed graph into a contiguous nucleotide sequence by concatenating the nucleotide sequences of the nodes forming the path,

aligning the contiguous nucleotide sequence with a reference sequence, and

identifying any differences between the aligned contiguous nucleotide sequence and the reference sequence as a variant.

15 . The method of claim 1 , wherein the directed graph is a directed acyclic graph.

16 . A computer system for use in identifying a genetic mutation, the system comprising:

a data source providing data representative of a plurality of nucleotide sequence reads mapping to a genomic region of interest; and

a processor communicatively coupled to the data source, the processor configured to:

create in computer memory a directed graph from the plurality of nucleotide sequence reads by:

(i) aligning a first sequence read of the plurality of nucleotide sequence reads to a second sequence read of said plurality and producing an alignment indicator;

(ii) defining at least one node of the directed graph as a function of the produced alignment indicator, each defined node representing a nucleotide sequence portion;

(iii) iteratively, for each remaining sequence read after the first and second sequence reads, aligning the remaining sequence read against the then defined directed graph and producing a respective alignment indicator that indicates a match to an existing node of the directed graph or that extends the directed graph by lengthening a node with additional nucleotide sequences, by adding new nodes to incorporate new sequence variations, or a combination thereof, the created directed graph providing a local assembly of the sequence reads;

perform variant calls with the created directed graph and a reference genome, the performing variant calls including detecting a variant, represented in a node of the directed graph, with respect to the reference genome; and

provide an output identifying a genomic mutation based on the detected variant.

17 . The computer system of claim 16 , wherein the processor is further configured to initially position the plurality of sequence reads with respect to a reference sequence and sort the plurality of sequence reads based on the position of said sequence reads with respect to the reference sequence, and wherein the iterative aligning iterates in order of the sequence reads resulting from said sort.

18 . The computer system of claim 16 , wherein the processor is further configured to create the directed graph in computer memory by aligning the first sequence read to a reference sequence prior to the alignment of the second sequence read to the first sequence read.

19 . The computer system of claim 17 , wherein the reference sequence is a linear or graph reference genome.

20 . The computer system of claim 17 , wherein the processor is further configured to perform variant calls at the initial positioning, resulting in a first set of variant calls.

21 . The computer system of claim 20 , wherein the processor is further configured to determine the genomic region of interest by the first set of variant calls.

22 . The computer system of claim 17 , wherein the processor is further configured to sort the plurality of sequence reads by, for a paired-end sequence read that is unmapped to the reference genome, assigning a position to one of the unmapped sequence reads of a pair based on (i) position of the other sequence read of the pair, and (ii) an insert size defined as a function an inferred length of a DNA molecule that originated the paired-end sequence read.

23 . The computer system of claim 16 , wherein the wherein the processor is further configured to account for gaps between the first and second sequence reads during the alignment of the first sequence read to the second sequence read.

24 . The computer system of claim 16 , wherein:

the aligning of sequence reads employs a Smith-Waterman technique, a Graph-Smith-Waterman technique, or a graph-aware optimal alignment algorithm; and

the produced alignment indicator is a Compact Idiosyncratic Gapped Alignment Report (CIGAR) string.

25 . The computer system of claim 24 , wherein defining the nodes of the directed graph as a function of the produced CIGAR strings includes:

(i) if the CIGAR string indicates the first and second sequence reads are identical, defining a single node in the directed graph, the single node representing the corresponding identical nucleotide sequence of the first and second sequence reads;

(ii) if the CIGAR string indicates the first and second sequence reads are overlapping, defining a single node in the directed graph representing the corresponding overlapping nucleotide sequences of the first and second sequence reads and any nonoverlapping tails of the first and second sequence reads; and

(iii) if the CIGAR string indicates the first and second sequence reads are a variation of each other, defining in the directed graph respective single nodes representing sequence portions in common and respective alternative nodes representing variations.

26 . The computer system of claim 16 , wherein defining the nodes of the directed graph as a function of the alignment indicator includes:

(i) if the alignment indicator indicates the first and second sequence reads are identical, defining a single node in the directed graph, the single node representing the corresponding identical nucleotide sequence of the first and second sequence reads;

(ii) if the alignment indicator indicates the first and second sequence reads are overlapping, defining a single node in the directed graph representing the corresponding overlapping nucleotide sequences of the first and second sequence reads and any nonoverlapping tails of the first and second sequence reads;

(iii) if the alignment indicator indicates the first and second sequence reads are a variation of each other, defining in the directed graph respective single nodes representing sequence portions in common and respective alternative nodes representing variations.

27 . The computer system of claim 16 , wherein the processor is further configured to prune the created directed graph by removing low-confidence nodes, wherein the low-confidence nodes represent a low number of mapped sequence reads or low-quality sequence reads.

28 . The computer system of claim 16 , wherein the processor is further configured to incorporate the created directed graph into a reference sequence and re-position the plurality of sequence reads to the updated reference sequence incorporating the created directed graph, rescuing unmapped and/or misaligned sequence reads.

29 . The computer system of claim 16 , wherein the processor is further configured to perform variant calls by:

transforming at least one path through the directed graph into a contiguous nucleotide sequence by concatenating the nucleotide sequences of nodes forming the path,

aligning the contiguous nucleotide sequence with a reference sequence, and

identifying any differences between the aligned contiguous nucleotide sequence and the reference sequence as a variant.

30 . The computer system of claim 16 , wherein the directed graph is a directed acyclic graph.

31 . A computer program product comprising:

a non-transitory computer readable medium; and

an executable program stored on the non-transitory computer readable medium, the program being for identifying a genetic mutation by:

accessing data representative of a plurality of nucleotide sequence reads mapping to a genomic region of interest;

creating in computer memory a directed graph from the plurality of nucleotide sequence reads, including:

(i) aligning a first sequence read of the plurality of nucleotide sequence reads to a second sequence read of said plurality and producing an alignment indicator;

(ii) defining at least one node of the directed graph as a function of the produced alignment indicator, the defined node representing a nucleotide sequence portion;

(iii) iteratively, for each remaining sequence read after the first and second sequence reads, aligning the remaining sequence read against the then defined directed graph and producing a respective alignment indicator that indicates a match to an existing node of the directed graph or that extends the directed graph by lengthening a node with additional nucleotide sequences, by adding new nodes to incorporate new sequence portions or variations, or a combination thereof, the created directed graph providing a local assembly of the sequence reads; and

performing variant calls with the created directed graph and a reference genome, the performing variant calls including detecting a variant, represented in a node of the directed graph, with respect to the reference genome; and

providing an output identifying a genomic mutation based on the detected variant.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 25, 2022
From: BROWNING, JOHN; KURAL, DENIZ
To: SEVEN BRIDGES GENOMICS, INC.
Reel/Frame 059402/0687 →
Continuity (3)
Continuation 15669141 · Aug 4, 2017
Provisional Application 62372020 · Aug 8, 2016
Related Publication 20220172800A1 · Jun 2, 2022
References Cited (273)
US 5511158A · Sims · 1996 [cited by applicant]
US 5701256A · Marr et al. · 1997 [cited by applicant]
US 6054278A · Dodge et al. · 2000 [cited by applicant]
US 6223128B1 · Allex et al. · 2001 [cited by applicant]
US 7577554B2 · Lystad et al. · 2009 [cited by applicant]
US 7580918B2 · Chang et al. · 2009 [cited by applicant]
US 7809509B2 · Milosavljevic · 2010 [cited by applicant]
US 7885840B2 · Sadiq et al. · 2011 [cited by applicant]
US 7917302B2 · Rognes · 2011 [cited by applicant]
US 8209130B1 · Kennedy et al. · 2012 [cited by applicant]
US 8340914B2 · Gatewood et al. · 2012 [cited by applicant]
US 8370079B2 · Sorenson · 2013 [cited by applicant]
US 8639847B2 · Blaszczak et al. · 2014 [cited by applicant]
US 9063914B2 · Kural et al. · 2015 [cited by applicant]
US 9092402B2 · Kural et al. · 2015 [cited by applicant]
US 9116866B2 · Kural · 2015 [cited by applicant]
US 9390226B2 · Kural · 2016 [cited by applicant]
US 9817944B2 · Kural · 2017 [cited by applicant]
US 11289177B2 · Browning et al. · 2022 [cited by applicant]
US 20040023209A1 · Jonasson · 2004 [cited by applicant]
US 20050089906A1 · Furuta et al. · 2005 [cited by applicant]
US 20060292611A1 · Berka et al. · 2006 [cited by applicant]
US 20070166707A1 · Schadt et al. · 2007 [cited by applicant]
US 20080077607A1 · Gatawood et al. · 2008 [cited by applicant]
US 20080294403A1 · Zhu et al. · 2008 [cited by applicant]
US 20090119313A1 · Pearce · 2009 [cited by applicant]
US 20090164135A1 · Brodzik et al. · 2009 [cited by applicant]
US 20090300781A1 · Bancroft et al. · 2009 [cited by applicant]
US 20100041048A1 · Diehi et al. · 2010 [cited by applicant]
US 20100169026A1 · Sorenson et al. · 2010 [cited by applicant]
US 20110004413A1 · Camevaii et al. · 2011 [cited by applicant]
US 20110098193A1 · Kingsmore et al. · 2011 [cited by applicant]
US 20120041727A1 · Mishra et al. · 2012 [cited by applicant]
US 20120045771A1 · Beier et al. · 2012 [cited by applicant]
US 20120239706A1 · Steinfadt · 2012 [cited by applicant]
US 20120330566A1 · Chaisson · 2012 [cited by applicant]
US 20130059738A1 · Leamon et al. · 2013 [cited by applicant]
US 20130059740A1 · Drmanac et al. · 2013 [cited by applicant]
US 20130073214A1 · Hyland et al. · 2013 [cited by applicant]
US 20130124100A1 · Drmanac · 2013 [cited by applicant]
US 20130289099A1 · Goff et al. · 2013 [cited by applicant]
US 20130311106A1 · White et al. · 2013 [cited by applicant]
US 20140025312A1 · Chin et al. · 2014 [cited by applicant]
US 20140051588A9 · Drmanac et al. · 2014 [cited by applicant]
US 20140066317A1 · Talasaz · 2014 [cited by applicant]
US 20140136120A1 · Colwell et al. · 2014 [cited by applicant]
US 20140200147A1 · Bartha et al. · 2014 [cited by applicant]
US 20140278590A1 · Abbassi et al. · 2014 [cited by applicant]
US 20140280360A1 · Webber et al. · 2014 [cited by applicant]
US 20140323320A1 · Jia et al. · 2014 [cited by applicant]
US 20150056613A1 · Kural · 2015 [cited by applicant]
US 20150057946A1 · Kural · 2015 [cited by applicant]
US 20150094212A1 · Gottirnukkaia et al. · 2015 [cited by applicant]
US 20150110754A1 · Bai et al. · 2015 [cited by applicant]
US 20150112602A1 · Kural et al. · 2015 [cited by applicant]
US 20150112658A1 · Kural et al. · 2015 [cited by applicant]
US 20150197815A1 · Kural · 2015 [cited by applicant]
US 20150199472A1 · Kural · 2015 [cited by applicant]
US 20150199473A1 · Kural · 2015 [cited by applicant]
US 20150199474A1 · Kural · 2015 [cited by applicant]
US 20150199475A1 · Kural · 2015 [cited by applicant]
US 20150227685A1 · Kural · 2015 [cited by applicant]
US 20150293994A1 · Kelly · 2015 [cited by applicant]
US 20150302145A1 · Kural et al. · 2015 [cited by applicant]
US 20150310167A1 · Kural et al. · 2015 [cited by applicant]
US 20150344970A1 · Vogelstein et al. · 2015 [cited by applicant]
US 20150347678A1 · Kural · 2015 [cited by applicant]
US 20150356147A1 · Mishra et al. · 2015 [cited by applicant]
US 20160259880A1 · Sernenyuk · 2016 [cited by applicant]
US 20160306921A1 · Kural · 2016 [cited by applicant]
US 20160364523A1 · Locke et al. · 2016 [cited by applicant]
US 20170058320A1 · Locke et al. · 2017 [cited by applicant]
US 20170058341A1 · Locke et al. · 2017 [cited by applicant]
US 20170058365A1 · Locke et al. · 2017 [cited by applicant]
US 20170198351A1 · Lee et al. · 2017 [cited by applicant]
US 20170199959A1 · Locke · 2017 [cited by applicant]
US 20170199960A1 · Ghose et al. · 2017 [cited by applicant]
US 20170242958A1 · Brown · 2017 [cited by applicant]
US 20180039730A1 · Browning et al. · 2018 [cited by applicant]
WO WO2012096579A3 · 2012 [cited by applicant]
WO WO2012098515A1 · 2012 [cited by applicant]
WO WO2012142531A2 · 2012 [cited by applicant]
WO WO2015027050A1 · 2015 [cited by applicant]
WO WO2015048753A1 · 2015 [cited by applicant]
WO WO2015058093A1 · 2015 [cited by applicant]
WO WO2015058095A1 · 2015 [cited by applicant]
WO WO2015058097A1 · 2015 [cited by applicant]
WO WO2015058120A1 · 2015 [cited by applicant]
WO WO2015061099A1 · 2015 [cited by applicant]
WO WO2015061103A1 · 2015 [cited by applicant]
WO WO2015105963A1 · 2015 [cited by applicant]
WO WO2015123269A1 · 2015 [cited by applicant]
WO WO2016141294A1 · 2016 [cited by applicant]
WO WO2016201215A1 · 2016 [cited by applicant]
WO WO2017120128A1 · 2017 [cited by applicant]
WO WO2017123864A1 · 2017 [cited by applicant]
WO WO2017147124A1 · 2017 [cited by applicant]
Allam, A., Kalnis, P. and Solovyev, V. Karect: accurate correction of substitution, insertion and deletion errors for next-generation sequencing data. Bioinformatics, 31(21), pp. 3421-3428. (Year: 2015). [cited by examiner]
Durbin, R. et al., “Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids,” Cambridge University Press 1999. [cited by applicant]
Smith, T.F. et al., “Identification of Common Molecular Subsequences,” J. Mol. Biol., 147(1):195-197, 1981. [cited by applicant]
Gotoh, O., “An Improved Algorithm for Matching Biological Sequences,” J. Mol. Biol., 162(3):705-708, 1982. [cited by applicant]
Zerbino, D. R. et al., : Velvet: Algorithms for De Novo Short Read Assembly Using De Bruijn Graphs, Cold Spring Harbor Laboratory Press, 18:821-829, 2008. [cited by applicant]
Broad Institute Genome Analysis Toolkit (GATK): https://www.broadinstitute.org/gatk/guide/topic?namc=methods. [cited by applicant]
Agarvval, 2013, SINNET: Social interaction Network Extractor from Text, Proc IJCNLP 33-36. [cited by applicant]
Aguiar, 2012, HapCompass: A fast cycle basis algorithm for accurate haplotype assembly of sequence data, J Comp D Biol 19(6):577-590. [cited by applicant]
Aguiar, 2013, Haplotype assembly in polyploid genomes and identical by descent shared tracts, Bioinformatics 29(13): i352-i360. [cited by applicant]
Airoldi, 2008, Mixed membership stochastic blockmodels, JMLR 9 1981-2014. [cited by applicant]
Albers, 2011, Dindel: Accurate indel calls from short-read data, Genome Research 21 :961-973. [cited by applicant]
Alioto et al., A comprehensive assessment of somatic mutation detection in cancer using whole-genome sequencing, Nature Communications, Dec. 9, 2015. [cited by applicant]
Altera, 2007, Implementation of the Smith-Waterman algorithm on reconfigurable supercomputing platform, White Paper per 1.0 (18 pages). [cited by applicant]
Altschul, 1986, Optimal Sequence Alignment Using Affine Gap Costs, Bull Math Biol 48(5/6):603-616. [cited by applicant]
Bansal, 2008, An MCMC algorithm for haplotype assembly from whole-genome sequence data, Genome Res 18:1336-1346. [cited by applicant]
Bao, 2013, BRANCH: boosting RNA-Seq assemblies with partial or related genomic sequences, Bioninformatics 29 (10): 1250-1259. [cited by applicant]
Barbieri, 2013, Exome sequencing identifies recurrent SPOP, FOXA1 and MED12 mutations in prostate cancer, Nature Genetics 44:6 685-689. [cited by applicant]
Beerenwinkel, 2007, Conjunctive Bayesian Networks, Bernoulli 13(4), 893-909. [cited by applicant]
Berlin, 2014, Assembling large genomes with single-molecule sequencing and locality sensitive hashing, bioRxiv preprint (35 pages); retrieved from the internet on Jan. 29, 2015. [cited by applicant]
Bertrand, 2009, Genetic map refinement using a comparative genomic approach, J Comp Biol 16(10) 1475-1486. [cited by applicant]
Black, 2005, A simple answer for a splicing conundrum, PNAS 102:4927-8. [cited by applicant]
Boyer, 1977, A Fast String Searching Algorithm, Comm ACM 20(10):762-772. [cited by applicant]
Browning et al., Haplotype phasing: existing methods and new developments, 2011, vol. 12, Nature Reviews Genetics. [cited by applicant]
Caboche et al., Comparison of mapping algorithms used in high-throughput sequencing: application to Ion Torrent data, 2014, vol. 15, BMC Genomics. [cited by applicant]
Cartwright, DNA assembly with gaps (DAWG): simulating sequence evolution, 2005, pp. iii31-iii38, vol. 21, Oxford University Press. [cited by applicant]
Chang, 2005, The application of alternative splicing graphs in quantitative analysis of alternative splicing form from EST database, Int J Comp Appl Tech 22(1 ): 14. [cited by applicant]
Chin, 2013, Nonhybrid finished microbial genome assemblies from long-read SMRT sequencing data, Nat Meth 10 (6):563-569. [cited by applicant]
Chuang, 2001, Gene recognition based on DAG shortest paths, Bioinformatics 17(Suppl. 1):s56-s64. [cited by applicant]
Compeau, 2011, How to apply de Bruljn graphs to genome assembly, Nat 8iotect1 29(11):987-991. [cited by applicant]
Craig, 1990, Ordering of cosmid clones covering the Herpes simplex virus type 1 (HSV-I) genome: a test case for fingerprinting by hybridisation, Nucleic Acids Research 18:9 pp. 2653-2660. [cited by applicant]
Denoeud, 2004, Identification of polymorphic tandem repeats by direct comparison of genome sequence from different bacterial strains: a web-based resource, BMC Bioinformatics 5:4 pp. 1-12. [cited by applicant]
Depristo, 2011, A framework for variation discovery and genotyping using next-generation DNA sequencing data, Nat Gen 43:491-498. [cited by applicant]
Duan et al., Optimizing de novo common wheat transcriptome assembly using short-read RNA-Seq data. (2012) pp. 1-12, vol. 13, BMC Genomics. [cited by applicant]
Dudley, 2009, A quick guide for developing effective bioinformatics programming skills, PLoS Comput Biol 5(12): e1000589. [cited by applicant]
Durbin, 2014, Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (PBWT), Bioinformatics 30(9):1266-1272. [cited by applicant]
Endelman, 2011, New algorithm improves fine structure of the barley consensus SNP map, Bl'v1C Genomics 12(1):407 (and whole document). [cited by applicant]
Exam Report issued in EP14803268.3. [cited by applicant]
Examination Report issued in Sg 11201601124Y. [cited by applicant]
Extended European Search Report issued in EP 14837955.5. [cited by applicant]
Extended European Search Report issued in EP 14847490.1. [cited by applicant]
Extended European Search Report issued in EP 14854801.9. [cited by applicant]
Farrar, 2007, Striped Smith-Waterman speeds database searches six times over other Si MD implementations, Bioinformatics 23(2):156-161. [cited by applicant]
Fitch, 1970, Distinguishing homologous from analogous proteins, Systematic Zoology 19:99-113. [cited by applicant]
Flicek, 2009, Sense from sequence reads: methods for alignment and assembly, Nat Meth Suppl 6(11s):s6-s12. [cited by applicant]
Florea, 2013, Genome-guided transcriptome assembly in the age of next-generation sequencing, IEEE/ACM Trans Comp Biol Bioinf 10(5):1234-1240. [cited by applicant]
Garber, 2011, Computational methods for transcriptome annotation and quantification using RNA-Seq, Nat Meth 8 (6):469-4 77. [cited by applicant]
Gerlinger, 2012, Intratumor Heterogeneity and Branched Evolution Revealed by Multiregion Sequencing, 366:10 883-892. [cited by applicant]
Golub, 1999, Molecular classification of cancer class discovery and class prediction by gene expression monitoring, Science 286, pp. 531-537. [cited by applicant]
Gotoh, 1982, An improved Algorithm for Matching Biological Sequences, J Mol Biol 162:705-708. [cited by applicant]
Gotoh, 1999, Multiple sequence alignment: algorithms and applications, Adv Biophys 36:159-206. [cited by applicant]
Grabherr, 2011, Full-length transcriptome assembly from RNA-Seq data without a reference genome, Nat Biotech 29 (7):644-654. [cited by applicant]
Grasso, 2004, Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems, Bioinformatics 20(10):1546-1556. [cited by applicant]
Guttman, 2010, Ab initio reconstruction of celi type-specific transcriptomes in mouse reveals the conserved multi-exonic structure of lincRNAs, Nat Biotech 28(5):503-510. [cited by applicant]
Guttman, 2010, Ab initio reconstruction of transcriptomes of pluripotent and lineage committed cells reveals gene structures of thousands of lincRNAs, NIH-PA Author Manuscript. [cited by applicant]
Haas, 2004, DAGchainer: a tool for mining segmental genome duplications and synteny, Bioinformatics 20 (18):3643-3646. [cited by applicant]
Harrow, 2012, GENCODE: The reference human genome annotation for The ENCODE Project, Genome Res 22: 1760-1774. [cited by applicant]
He, 2010, Optimal algorithms for haplotype assembly from whole-genome sequence data, Bioinformatics 26:i183-i190. [cited by applicant]
Heber, 2002, Splicing graphs and EST assembly problems, Bioinformatics 18 Suppl:181-188. [cited by applicant]
Hein, 1989, A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences when the phylogeny is given, Mol Biol Evol 6(6):649-668. [cited by applicant]
Hein, 1989, A tree reconstruction method that is economical in the number of pairwise comparisons used, Mol Biol Evol 6(6):649-668. [cited by applicant]
Horner, 2010, Improved variant discovery through local re-alignment of short-read next generation sequencing data using SRMA, Genome Biol 11 (1 0):R99. [cited by applicant]
Horspool, 1980, Practical Fast Searching in Strings, Software—Practice & Experience 10:501-506. [cited by applicant]
Huang, Chapter 3: Bio-Sequence Comparison and Alignment, ser. Curr Top Comp Mol Biol. Cambridge, Mass. The MIT Press, 2002. [cited by applicant]
Hutchinson, 2014, Allele-specific methylation occurs at genetic variants associated with complex diseases, PLoS One 9(6):e98464. [cited by applicant]
International Search Report and Written Opinion mailed Aug. 31, 2017, for International Application No. PCT/ US2017/018830 with International Filing Date Feb. 22, 2017, (11 pages), title Systems and Methods for Genotypi… [cited by applicant]
International Search Report and Written Opinion mailed Mar. 31, 2015 for International Application No. PCT/ US2015/010604 (Client Ref SBG-010/01 WO) filed Jan. 8, 2015 (13 pages), title Systems and Methods for Use of Kn… [cited by applicant]
International Search Report and Written Opinion mailed Apr. 19, 2017 for international Patent Application No. PCT/ US2017/012015, (14 Pages), title Systems and Methods for Adaptive Local Alignment for Graph Genomes. [cited by applicant]
International Search Report and Written Opinion mailed Feb. 17, 2015, for International Patent Application No. PCT/US2014/061156, filed Oct. 17, 2014 (19 pages), title Methods and Systems for Genotyping Genetic Samples. [cited by applicant]
International Search Report and Written Opinion mailed Jan. 10, 2017, for International Patent Application No. PCT/US16/57324 with International Filing Date Oct. 17, 2016, (7 pages), title Biological Graph or Sequence S… [cited by applicant]
International Search Report and Written Opinion mailed Mar. 19, 2015, for international Application No. PCT/ US2014/061162 with International Filing Date Oct. 17, 2014, (12 pages), title Methods and Systems for Identify… [cited by applicant]
International Search Report and Written Opinion mailed May 11, 2015, for International Patent Application No. PCT/ US2015/015375 with International Filing Date Feb. 11, 2015, (12 pages), title System and Methods for Ana… [cited by applicant]
International Search Report and Written Opinion mailed May 5, 2016, for International Patent Application No. PCT/ US2016/020899, with International Filing Date Mar. 4, 2016, (12 pages), title Systems and Methods for Gen… [cited by applicant]
International Search Report and Written Opinion mailed on Apr. 7, 2017, for International Patent Application No. PCT/US2017/013329, filed Jan. 13, 2017, (9 pages), title Systems and Methods for Analyzing Circulating Tum… [cited by applicant]
International Search Report and Written Opinion mailed on Dec. 11, 2014, for International Patent Application No. PCT/US14/52065, filed Aug. 21, 2014, (18 pages), title, Methods and Systems for Aligning Sequences. [cited by applicant]
International Search Report and Written Opinion mailed on Dec. 30, 2014, for International Patent Application No. PCT/US14/58328, filed Sep. 30, 2014, (22 pages), title Methods and System for Detecting Sequence Variants. [cited by applicant]
International Search Report and Written Opinion mailed on Feb. 4, 2015, for International Patent Application No. PCT/US2014/061198, filed Oct. 17, 2014, (8 pages), title Methods and Systems for Aligning Sequences in the… [cited by applicant]
International Search Report and Written Opinion mailed on Feb. 10, 2015, for International Patent Application No. PCT/US2014/060690, filed Oct. 15, 2014, PCT/US2014/060690 (11 pages), title Systems and Methods for Using… [cited by applicant]
International Search Report and Written Opinion mailed on Feb. 4, 2015, for Patent Application No. PCT/ US2014/061158, filed Oct. 17, 2014, (11 pages), title Methods and Systems for Quantifying Sequence Alignment. [cited by applicant]
International Search Report and Written Opinion mailed on Jan. 27, 2015, for International Patent Application No. PCT/US2014/060680, filed October 215, 2014, (11 pages), title Systems and Methods for Transcriptome Analy… [cited by applicant]
International Search Report and Written Opinion mailed Sep. 2, 2016, for International Patent Application No. PCT/US2016/033201 with International Filing Date May 19, 2016, (14 pages), title Systems and Methods for Hapl… [cited by applicant]
International Search Report and Written Opinion mailed Sep. 7, 2016, for International Application No. PCT/ US2016/036873 with International filing date Jun. 10, 2016, (8 pages), title Systems and Methods for Identifyin… [cited by applicant]
Kano, 2010, Text mining meets workflow: linking U-Compare with Taverna, Bioinformatics 26(19):2486-7. [cited by applicant]
Kehr, 2014, Genome alignment with graph data structures: a comparison, BMC Bioinformatics 15:99. [cited by applicant]
Kent, 2002, BLAT-The Blast-Like Alignment Tool, Genome Research 4:656-664. [cited by applicant]
Kim, 2005, ECgenc: Genome-based EST clustering and gone modeling for alternative splicing, Genome Res 15:566-576 Kim, 2008, A Scaffold Analysis Tool Using Mate-Pair Information in Genome Sequencing, Journal of Biomedici… [cited by applicant]
Kim, 2013, TopHat2: accurate alignment of transcriptomes in the presence of insertions, deletions and gene fusions, Genome Biol 14(4):R36. [cited by applicant]
Koolen, 2008, Clinical and Molecular Delineation of the 17q21.31 Microdeletion Syndrome, J Med Gen 45(11):710-720. [cited by applicant]
Kumar, 2010, Comparing de novo assemblers for 454 transcriptome data, BMC Genornics 11 :571. [cited by applicant]
Kurtz, 2004, Versatile and open software for comparing large genomes, Genome Biol 5:R12. [cited by applicant]
Lam, 2008, Compressed indexing and local alignment of DNA, Bioinformatics 24(6):791-97. [cited by applicant]
Lang mead, 2009, Ultrafast and memory-efficient alignment of short DNA sequences to the human genome, Genome Biol 10:R25. [cited by applicant]
Larkin, 2007, Clustal Wand Clustal X version 2 0, Bioinformatics 23(21):2947-2948. [cited by applicant]
Lecca, 2015, Defining order and timing of mutations during cancer progression: the TO-DAG probabilistic graphical model, Frontiers in Genetics, vol. 6 Article 309 1-17. [cited by applicant]
Lee et al. Accurate read mapping using a graph-based human pan-genome. (May 2015) American Society of Human Genetics 64th Annual Meeting Platform Abstracts; Abstract 41. [cited by applicant]
Lee, 2002, Multiple sequence alignment using partial order graphs, Bioinformatics 18(3):452-464. [cited by applicant]
Lee, 2005, Bioinformatics analysis of alternative splicing, Brief Bioinf 6(1 ):23-33. [cited by applicant]
Lee, 2014, Accurate read mapping using a graph-based human pan-genome, ASHG 2014 Abstracts. [cited by applicant]
Legault, 2010, Learning Probalistic Splice Graphs from RNA-Seq data, pages.cs.wisc.eduHegauit/cs760_writeup.pdf; retrieved from the internet on Apr. 6, 2014. [cited by applicant]
Lcgault, 2013, Inference of alternative splicing from RNA-Scq data with probabilistic splicc graphs, Bioinformatics 29 (18):2300-2310. [cited by applicant]
Leipzig, 2004, The alternative splicing gallery (ASG): Bridging the gap between genome and transcriptome, Nuc Acids Res 23(13):3977-3983. [cited by applicant]
Li, 2009, Fast and accurate short read alignment with Burrows-Wheeler Transform. Bioinformatics 25:1754-60. [cited by applicant]
Li, 2010, A survey of sequence alignment algorithms for next-generation sequencing, Briefings in Bionformatics 11 (5) :4 73-483. [cited by applicant]
Lipman, 1985, Rapid and sensitive protein similarity searches, Science 227(4693): 1435-41. [cited by applicant]
Lucking, 2011, PICS-Ord: unlimited coding of ambiguous regions by pairwise identity and cost scores ordination, BMC Bio inf 12: 10. [cited by applicant]
Lupski, 2005, Genomic disorders: Molecular mechanisms for rearrangements and conveyed phenotypes, PLoS Genetics 1 (6):e49. [cited by applicant]
Ma, 2010, Multiple genome alignment based on longest path in directed acyclic graphs, Int J Bioinformatics 6 (4):366-683. [cited by applicant]
Mamoulis, 2004, Non-contiguous sequence pattern queries, in Advances in Database Technology—EDBT 2004: 9th. [cited by applicant]
International Conference on Extending Database Technology, Heraklion, Crete, Greece, Mar. 14-18, 2004, Proceedings (18 pages); retrieved from the internet on Jun. 3, 2016. [cited by applicant]
Marth et al., 1999—A general approach to single-nucleotide polymorphism discovery, pp. 452-456, vol. 23, Nature Genetics. [cited by applicant]
Mazrouee, 2014, FastHap: fast and accurate single individual haplotype reconstructions using fuzzy conflict graphs, Bioinformatics 30:i371-i378. [cited by applicant]
Mcsherry, 2001, Spectral partitioning of random graphs, Proc 42nd IEEE Symp Found Comp Sci 529-537. [cited by applicant]
Miller, 2010, Assembly Algorithms for Next-Generation Sequencing Data, Genomics 95(6):315-327. [cited by applicant]
Mount, 2001, Multiple Sequence Alignment, Bioinformatics, 2001, Cold Spring Harbor Laboratory Press, Cold Spring Harbor, New York, pp. 139-204. [cited by applicant]
Mourad, 2012, A hierarchical Bayesian network approach for linkage disequilibrium modeling and data-dimensionality reduction prior to genome-wide association studies, BMC Bioinformatics 12:16 1-20. [cited by applicant]
Myers, The Fragment Assembly String Graph, Bioinformatics, 2005, pp. ii79-ii85, vol. 21. [cited by applicant]
Nagarajan, 2013, Sequence assembly demystified, Nat Rev 14:157-167. [cited by applicant]
Nakao, 2005, Large-scale analysis of human alternative protein isoforms: pattern classification and correlation with subcellular localization signals, Nucl Ac Res 33(8):2355-2363. [cited by applicant]
Needleman, 1970, A general method applicable to the search for similarities in the amino acid sequence of two proteins, J Mol Biol 48(3):443-453. [cited by applicant]
Newman, 2013, Community detection and graph portioning, Europhys Lett 103(2):28003, arXiv:1305.4974v1. [cited by applicant]
Newman, 2014, An ultrasensitive method for quantitating circulating tumor DNA with broad patient coverage, Nature Medicine 20:5 1-11. [cited by applicant]
Olsson, 2015, Serial monitoring of circulating tumor DNA in patients with primary breast cancer for detection of occult metastatic disease, EMBO Molecular Medicine 7:8 1034-104 7. [cited by applicant]
Oshlack, 2010, From RNA-seq reads to differential expression results. Genome Bio 11 :220. [cited by applicant]
Parks, 2015, Detecting non-allelic homologous recombination from high-throughput sequencing data, Genome Biol 16:17. [cited by applicant]
Peixoto, 2014, Efficient Monte Caria and greedy heuristic for the inference of stochastic block models, Phys. Rev. E 89, 012804. [cited by applicant]
Pop et al., 2004, Comparative genome assembly, Briefings in Bioinformatics vol. 5, pp. 237-248. [cited by applicant]
Pruesse, 2012, SINA: Accurate high-throughput multiple sequence alignment of ribosomal RNA genes, Bioinformatics 28: 14 1823-1829. [cited by applicant]
Rajaram, 2013, Pearl millet [ [cited by applicant]
Raphael, 2004, A novel method for multiple alignment of sequences with repeated and shuffled elements, Genome Res 14:2336-2346. [cited by applicant]
Robertson, 2010, De novo assembly and analysis of RNA-seq data, Nat Meth 7(11 ):909. [cited by applicant]
Rodelsperger, 2008, Syntenator: Multiple gene order alignments with a gene-specific scoring function, Alg Mol Biol 3:14. [cited by applicant]
Rognes, 2000, Six-fold speed-up of Smith-Waterman sequence database searching using parallel processing on common microprocessors, Bioinformatics 16(8) :699-706. [cited by applicant]
Rogncs, 2001, ParAlign: a parallel sequencc alignment algorithm for rapid and sensitive database searches, Nucl Ac Res 29(7):1647-1652. [cited by applicant]
Rognes, 2011, Faster Smith-Waterman database searches with inter-sequence SIMD parailelisation, Bioinformatics 12:221. [cited by applicant]
Ronquist, 2012, MrBayes 3.2 efficient Bayesian phylogenetic inference and model choice across a large model space, Syst Biol 61 (3):539-42. [cited by applicant]
Saebo, 2005, PARALIGN: rapid and sensitive sequence similarity searches powered by parallel computing technology, Nucl Ac Res 33:W535-W539. [cited by applicant]
Sato, 2008, Directed acyclic graph kernels for structural RNA analysis, BMC (BioMed Central) Bioinformatics 9(318). [cited by applicant]
Schneeberger, 2009, Simultaneous alignment of short reads against multiple genomes, Genome Biol 10(9):R98.2-R98.12. [cited by applicant]
Schwikowski, 2002, Weighted sequence graphs: boosting iterated dynamic programming using locally suboptimal solutions, Disc Appl Mat 127:95-117. [cited by applicant]
Shao, 2006, Bioinformatic analysis of exon repetition, exon scrambling and trans-splicing in humans, Bioinformatics 22: 692-698. [cited by applicant]
Shendure et al. Next-generation DNA sequencing Nature Biotechnology vol. 26, pp. 1135-1145 (2008). [cited by applicant]
Sievers, 2011, Fast, scalabie generation of high-quality protein multiple sequence alignments using Clustal Omeag, Mol Syst Biol 7:539. [cited by applicant]
Slater, 2005, Automated generation of heuristics for biological sequence comparison, BMC Bioinformatics 6:31. [cited by applicant]
Smith, 2012, Multiple insert size paired-end sequencing for deconvolution of complex transcriptions, RNA Bio 9(5) 596-609. [cited by applicant]
Sosa, 2012, Next-Generation Sequencing of Human Mitochondrial Reference Genomes Uncovers High Heteroplasmy Frequency, PLoS One 8(1O):e1002737. [cited by applicant]
Sturgeon, RCDA: a highly sensitive and specific alternatively spliced transcript assembly tool featuring upstream consecutive exon structures, Genomics, Dec. 2012, 100(6) 357-362. [cited by applicant]
Subramanian, 2008, DIAUGN-TX: greedy and progressive approaches for segment-based multiple sequence alignment, Alg Moi Biol 3(1):1-11. [cited by applicant]
Sudmant, 2015, An integrated map of structural variation in 2,504 human genomes, Nature 526 75-81. [cited by applicant]
Sun, 2006, Pairwise Comparison Between Genomic Sequences and Optical maps, dissertation, New York University (131 pages); retrieved from the internet on Jun. 3, 2016. [cited by applicant]
Szalkowski, 2012, Fast and robust multiple sequence alignment with phylogeny-aware gap placement, BMC (BioMed Central) Bioinformatics 13(129). [cited by applicant]
Szalkowski, 2013, Graph-based modeling of tandem repeats improves global multiple sequence alignment, Nucl Ac Res 41(17):e162. [cited by applicant]
Tarhio, 1993, Approximate Boyer-Moore String Matching, Siam J Comput 22(2):243-260. [cited by applicant]
Thomas, 2014, Community-wide effort aims to better represent variation in human reference genome, Genome Web (11 pages). [cited by applicant]
Trapnell, 2009, To pH at: discovering splice junctions with RNA-Seq, Bioinformatics 25: 1105-1111. [cited by applicant]
Trapnell, 2010, Transcript assembly and abundance estimation from RNA-Seq reveals thousands of new transcripts and switching among isoforms, Nat Biotech 28(5):511-515. [cited by applicant]
Trapnell, 2010, Transcript assembly and quantification by RNA-Seq reveals unannotated transcripts and isoform switching during cell differentiation, Nat Biotech 28(5):511-515. [cited by applicant]
Uchiyama et al., CGAT: a comparative genome analysis tool for visualizing alignments in the analysis of complex evolutionary changes between closely related genomes, 2006, e-pp. 1-17, vol. 7:472; BMC Bioinformatics. [cited by applicant]
Wang, 2009, RNA-Seq: a revolutionary tool for transcriptomics, Nat Rev Genet 10(1):57-63. [cited by applicant]
Written Opinion issued in SG 11201601124Y. [cited by applicant]
Written Opinion issued in SG 11201602903X. [cited by applicant]
Written Opinion issued in SG 11201603039P. [cited by applicant]
Written Opinion issued in SG 11201603044S. [cited by applicant]
Written Opinion issued in SG 112016055060. [cited by applicant]
Wu, 2010, Fast and SNP-tolerant detection of complex variants and splicing in short reads, Bioinformatics, 26 (7):873-881. [cited by applicant]
Xing, 2006, An expectation-maximization algorithm for probabilistic reconstructions of full-length isoforms from splice graphs, Nucleic Acids Research, 34:3150-3160. [cited by applicant]
Yang, 2013, Leveraging reads that span multiple single nucleotide polymorphisms for haplotype inference from sequencing data, Bioinformatics 29(18):2245-2252. [cited by applicant]
Yanovsky, 2008, Read mapping algorithms for single molecule sequencing data, Proc 8th Int Workshop Alg Bioinformatics 5251 :38-49. [cited by applicant]
Yu, 2010, The construction of a tetraploid cotton genome wide comprehensive reference map, Genomics 95:230-240. [cited by applicant]
Zeng, 2013, PyroHMMvar: a sensitive and accurate method to call short indels and SNPs for Ion Torrent and 454 data, Bioinformatics 29:22 2859-2868. [cited by applicant]
Zhang et al., Construction of a high-density genetic map for sesame based on large scale marker development by specific length amplified fragment (SLAF) sequencing. (2013) pp. 1-12, vol. 13, BMC Plant Biology. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 15/669,141, consisting of 40 pages. Mailed Apr. 5, 2019. [cited by applicant]
Final Office Action for U.S. Appl. No. 15/669,141, consisting of 12 pages. Mailed Nov. 15, 2019. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 15/669,141, consisting of 12 pages. Mailed Jun. 16, 2020. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 15/669,141, consisting of 11 pages. Mailed Jun. 25, 2021. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 15/669,141, consisting of 9 pages. Mailed Nov. 22, 2021. [cited by applicant]
Supplemental Notice of Allowance for U.S. Appl. No. 15/669,141, consisting of 35 pages. Mailed Dec. 7, 2021. [cited by applicant]
Lee, 2003, Generating consensus sequences from partial order multiple sequence alignment graphs, Bioinformatics 19(8):999-1008. [cited by applicant]