METHOD AND SYSTEM FOR PREDICTING AN EVENT OR CONDITION

The present disclosed subject provides Big Data analytics for various fields such as, quality assurance, event probabilities, statistical process control (SPC), finance, e-commerce, insurance and additional bio-informatics applications. The method utilizes “Big Data” analysis to rapidly and accurately calculate the probabilities of certain “TYPES”, which include, for example sets of objects, traits, events, and the like.

FIELD AND BACKGROUND OF THE INVENTION

The present invention, in some embodiments thereof, relates to bioinformatics and, more particularly, but not exclusively, to a method and system for predicting a disease by computational analysis of a DNA sequence.

Informatics is the study and application of computer and statistical techniques for the management of information. In Genome projects, bioinformatics includes the development of methods to search databases fast and efficiently, to analyze nucleic acid sequence information and to predict protein primary, secondary and tertiary structures from Deoxyribonucleic acid (DNA) sequence data. Increasingly, molecular biology is shifting from the laboratory bench to the computer desktop. Advanced quantitative analyses, database comparisons and computational algorithms are needed to explore the relationships between sequence, structure and phenotype.

DNA is the basic building block of life. DNA includes various nucleic acids, constructed of a double helix held together by hydrogen bonds between purine and pyrimidine bases which project inward from two chains containing alternate links of deoxyribose and phosphate. The DNA contains genetic instructions which are the basis of the development and function of most life forms, particularly mammals, e.g., humans. DNA is composed of molecules called nucleotides that when joined together form the structure of DNA. In DNA, nucleic acids are made from nucleotide constructions. There are four basic nucleotide structures, adenine (A), guanine (G), thymine (T), and cytosine (C), where A pairs with T, and C pairs with G. These pairings of complementary bases within a DNA strand are referred to as base pairs. DNA is further packaged with histones, in a larger scale, into a structure called a chromosome. A chromosome is a single piece of supercoiled DNA which contains, among other elements, genetic information, such as genes, regulatory elements, and transportable elements. A human genome contains 22 autosomes and a pair of sex chromosome (X and Y in male, and two Xs in female).

A gene is the genetic information unit of heredity in an individual consisting of a sequence of DNA and determines a particular characteristic of an organism. A gene can be defined as a locatable or fixed region of genomic sequence, corresponding to a unit of inheritance, which is associated with regulatory regions, transcribed regions, and or other functional sequence regions. Genes contain information for regulating, building and maintaining a human's cells and also pass genetic traits to offspring. All humans have genes which correspond to various traits, some of which are visible (phenotype), as in the case of eye or hair color, and some are not readily visible (genotype). A genotype is the genetic make-up of an organism or group of organisms with reference to a single trait, set of traits, or an entire complex of traits. A phenotype is the appearance of an organism resulting from the interaction of the genotype and the environment, such as eye or hair color.

A gene can have a variation or mutation, which is called an allele. An allele is one of two or more forms of a gene that have the same relative position on homologous chromosomes and are responsible for alternative characteristics. Humans are diploid, meaning they have two sets of chromosomes. In turn, this means they may have two variations of any given gene, alleles. Homologous chromosomes are chromosome pairs which share, among other things, the same length and contain genes for the same characteristics at corresponding loci, alleles. A locus is the specific location of a gene on a chromosome. Diploid organisms have one copy of each gene, therefore one allele, on each chromosome at corresponding loci. Each individual inherits two copies of DNA, one maternal and one paternal. If the alleles are the same, sharing the same mutation or lack thereof, they are referred to as homozygous. If the alleles are different, where one is mutated and one is not, they are referred to as heterozygous.

While the identity and sequences of many base pairs has now been worked out, little is yet known about which of these base sequences are responsible for which proteins and bodily functions, or which of these base sequences are implicated in treating disease. To the bioinformatics computer scientist, the human genome represents a vast data-mining project that holds profound promise to cure disease and prolong lives. The current approach to data-mining involves applying statistical methods and pattern recognition algorithms upon the genome database to make predictions about the information that is locked in the DNA.

Several computational techniques for handling gnome data are disclosed in International Publication Nos. WO2002036812, WO2013005173, WO2013119562, U.S. Pat. Nos. 6,651,008 and 8,296,116, and U.S. Published Application No. 20130311106.

SUMMARY OF THE INVENTION

According to an aspect of some embodiments of the present invention there is provided a method of estimating a likelihood of developing a disease. The method comprises performing the following operations on a data processor. Obtaining a set of gene sequences corresponding to the disease; obtaining a DNA sequence of a subject; for each gene sequence of the set, searching over the DNA sequence for reoccurrences of the gene sequence, and calculating an average reoccurrence distance between adjacent reoccurrences of the gene sequence; and estimating the likelihood of the subject to develop the disease, based on the calculated distances.

According to some embodiments of the invention the method further comprises randomly selecting a starting position over the DNA sequence, wherein the searching is initiated at the selected starting position.

According to some embodiments of the invention the method further comprises randomly selecting a plurality of starting positions over the DNA sequence, wherein the search is initiated a respective plurality of times, each time at a different selected starting position.

According to some embodiments of the invention the search is terminated when a predetermined number of reoccurrences is found.

According to some embodiments of the invention the predetermined number of reoccurrences is 1.

According to an aspect of some embodiments of the present invention there is provided a system for estimating a likelihood of developing a disease, the system comprise a data processor configured for: obtaining from a database a set of gene sequences corresponding to the disease; obtaining a DNA sequence of a subject; for each gene sequence of the set, searching over the DNA sequence for reoccurrences of the gene sequence, and calculating an average reoccurrence distance between adjacent reoccurrences of the gene sequence; and estimating the likelihood of the subject to develop the disease, based on the calculated distances.

According to an aspect of some embodiments of the present invention there is provided a computer software product. The computer software product comprises a non-volatile computer-readable medium in which program instructions are stored, which instructions, when read by a data processor, cause the data processor: to receive a DNA sequence of a subject, and a set of gene sequences corresponding to a disease; to search over the DNA sequence for reoccurrences of a gene sequence for each gene sequence of the set, and to calculate an average reoccurrence distance between adjacent reoccurrences of the gene sequence; and to estimate the likelihood of the subject to develop the disease, based on the calculated distances.

According to some embodiments of the invention the likelihood is estimated based on a set average distance calculated over the set.

According to some embodiments of the invention the instructions cause the data processor to randomly select a starting position over the DNA sequence, wherein the searching is initiated at the selected starting position.

According to some embodiments of the invention the instructions cause the data processor to randomly select a plurality of starting positions over the DNA sequence, wherein the searching is initiated a respective plurality of times, each time at a different selected starting position.

According to some embodiments of the invention the search is terminated when a predetermined number of reoccurrences is found.

According to some embodiments of the invention the predetermined number of reoccurrences is 1.

According to an aspect of some embodiments of the present invention there is provided a method of constructing a database of disease related genes. The method comprises performing the following operations on a data processor: obtaining a DNA sequence of a subject identified as having a disease, and a set of gene sequences associated with the DNA sequence; for each of at least a few gene sequences in the set, calculating an average reoccurrence distance between adjacent occurrences of the gene in the DNA; for at least one subset of gene sequences, determining a correlation between the subset and the disease, based, at least in part, on average reoccurrence distances of genes in the subset.

According to an aspect of some embodiments of the present invention there is provided a computer software product. The computer software product comprises a non-volatile computer-readable medium in which program instructions are stored, which instructions, when read by a data processor, cause the data processor: to obtain a DNA sequence of a subject identified as having a disease, and a set of gene sequences associated with the DNA sequence; to calculate, for each of at least a few gene sequences in the set, an average reoccurrence distance between adjacent occurrences of the gene in the DNA; to determine, for at least one subset of gene sequences, a correlation between the subset and the disease, based, at least in part, on average reoccurrence distances of genes in the subset.

According to some embodiments of the invention the correlation is determined based on a set average distance calculated over the subset.

According to some embodiments of the invention the correlation equals a reciprocal of the set average.

According to some embodiments of the invention the gene sequence is selected from the group consisting of an oncogene and a tumor suppressor gene.

According to some embodiments of the invention the disease is cancer.

DESCRIPTION OF SPECIFIC EMBODIMENTS OF THE INVENTION

The present invention, in some embodiments thereof, relates to bioinformatics and, more particularly, but not exclusively, to a method and system for predicting a disease by computational analysis of a DNA sequence.

Some embodiments of the present invention relate to a method and a system that estimates the likelihood of a subject, e.g., a mammalian subject, such as, but not limited to, a human subject, developing a disease. In some embodiments of the present invention the subject is an infant. In some embodiments of the present invention the subject is an embryo, and in some embodiments of the present invention the subject is a fetus.

Herein, “mammal” covers warm blooded mammals that are typically under medical care (e.g., humans and domesticated animals).

The method and system of some embodiments of the present invention perform genomic analysis of the subject, and estimate the likelihood to develop the disease based on the analysis.

As used herein, “genome” comprises whole (complete) genomes (e.g., whole cellular, and organelle genomes), and also includes portions of whole genomes having nucleic acid sequences sufficient to effect and/or sustain viability of a cell (minimal cellular genome), viability, within a host cell, of an organism that depends on a host cell for viability, or organelle function within a host cell (minimal organelle genome), under at least one set of environmental conditions. Thus, the term genome refers to whole genomes and portions thereof that are at least minimal genomes. The particular environmental conditions and property that is caused or sustained by the genome can be specified. In the case of an organelle, or other genome that depends on a host cell for propagation and viability, the environmental conditions can include the environment of a suitable and functional host cell. Thus, the term genome encompasses minimal genomes and minimal replicative genomes, and genomes containing additional nucleic acid sequences beyond those found in such minimal genomes but not containing all the nucleic acid sequences present in a whole genome.

As used herein “genomic DNA” refers to a chromosomal DNA containing coding and non-coding sequences.

Genomics is a field that encompasses various studies of the genome. Computationally, a sequence data is received and one or more computational operations are executed to determine or estimate the positions and identification of the genes (gene finding), and/or the similarity between the given sequence and another sequence (pair-wise sequence alignment), and/or the similarity among a set of given sequences (multiple sequence alignment), and/or the position at which another given bio-molecule bind (transcription factor binding site identification). Genomics can also attempt to compress the sequence, and/or to browse the genome.

The present embodiments may employ any of the above operations in order to estimate the likelihood of developing a disease. In particular, the present embodiments employ sequence alignment. In sequence alignment, two or more bio-sequences (DNA/RNA) are aligned so as to highlight their similarity to the maximum extent possible. An illustrative example is provided for linguistic sequences of alphabet. Consider, for example, the strings “Gates like cheese” and “Grated cheese”. Writing these strings one below the other, and performing letter-wise comparison, one finds only two letters matching, indicated by the symbol “I”.

However, if the sequences are stretched by inserting gaps, more matches can be found. The following example shows 10 matches.

Some embodiments of the present invention judicially apply such a technique to a DNA sequence, e.g., a genomic DNA sequence.

The present inventor found that a DNA sequence can be in probabilistically considered as a stationary ergodic process with finite value alphabet, which alphabet is conventionally denoted {A, T, C, G}. The present embodiments obtain a DNA sequence and estimates whether this sequence is mutated in a manner that the mutation increases the likelihood of developing a specific disease. This estimation is optionally and preferably performed by applying sequence alignment to search for sets of reference gene sequences in the DNA that match, or approximately match (with a predetermined probabilistic threshold), the specific disease.

The present embodiments can extract from the sequence alignment one or more parameters, including, without limitation, the rate of matching (e.g., the portion of the DNA that is modified by the disease), the accuracy of the matches as compared to the reference sequence (which is optionally and preferably correlated to the development stage of the expected development stage of the disease), and the position of the first match.

The search according to some embodiments of the present invention is optionally and preferably based on a technique known as “approximate string matching,” wherein an average distance measure between two potentially matched strings is calculated and compared to a predetermined threshold. The two strings are declared as an “approximate match” if the calculated average distance does not exceed the threshold. The distance can be the sum of the distances in each letter of the string.

In some embodiments, the distance can be the so called Hamming distance, which corresponds to the number of mismatches between the two strings. In the above example of the strings “Gates like cheese” and “Grated cheese,” the number of mismatches before stretching is 16 and the number of mismatches after stretching is 7, so the distance between the strings can be defined as 16 and 7, respectively.

The method and system of the present embodiments can be used to estimate the likelihood of developing many types of diseases, preferable gene-related diseases. Representative examples include, without limitation, a pathology characterized or associated with an abnormal or uncontrolled proliferation of cells and/or abnormal angiogenesis, a neurological disorder, a cardiovascular, endothelial or angiogenic disorder, an eye abnormality, an immunological disorder, an oncological disorder, a bone metabolic abnormality or disorder, a lipid metabolic disorder, a developmental abnormality and a chromosomal abnormality.

Representative examples of pathologies which involve abnormal cell proliferation and/or angiogenesis include, without limitation cancer (such as solid and hematologic tumors, e.g., metastatic cancer), cardiovascular diseases (such as atherosclerosis and restenosis), chronic inflammation (rheumatoid arthritis, Crohn's disease), diabetes (diabetic retinopathy), psoriasis, endometriosis, neovascular glaucoma and adiposity cardiovascular diseases; cirrhosis of the liver; connective tissue disorders (including those associated with ligaments, tendons, and cartilage); and a disease associated with collagen gene polynucleotide.

Additional examples of eye abnormalities including, without limitation, a cataract, such as, but not limited to, a cataract which is a systemic disease such as human Down's syndrome, Hallerman-Streiff syndrome, Lowe syndrome, galactosemia, Marfan syndrome, Trismoy 13-15, Alport syndrome, myotonic dystrophy, Fabry disease, hypoparathroidism or Conradi syndrome.

A representative example of developmental abnormality, includes, without limitation, embryonic lethality or reduced viability.

Representative examples of bone metabolic abnormality or disorder include, without limitation, arthritis, osteoporosis, osteopenia or osteopetrosis.

Representative examples of a disease associated with collagen gene polynucleotide include, without limitation a collagen disorder, age related collagen degradation, Osteogenesis imperfecta, Oto sclerosis (OTSC), Osteoporosis, Osteoarthritis, Oesophageal squamous cell cancer, chondrodysplasia, atypical Marfan syndrome, Ehlers-Danlos Syndrome (EDS), Dystrophic epidermolysis bullosa (DEB), Caffey disease, aneurysms (e.g. intracranial aneurysms), idiopathic pulmonary fibrosis, liver cirrhosis, kidney fibrosis, liver fibrosis, heart fibrosis, scleroderma, hypertrophic scars, keloids, cancer, inflammation, a genetic disease (e.g. Duchenne muscular dystrophy), a neurological disease or disorder (e.g. Parkinson's, Alzheimer's, Huntington's, Gaucher disease), a metabolic disease (e.g. type I diabetes), an autoimmune disease or disorder, trauma (e.g. spinal cord injury, burns, etc), ischemia, and other blood vessel, heart, a skin disease or disorder, skin aging, a skin disease or disorder or condition requiring skin engineering, a liver or kidney disease requiring transplantation; tendon, bone or tissue regeneration; skeletal repair, cartilage and bone repair.

The disease can also be a metabolic disease or disorder, such as, but not limited to, insulin resistance, diabetes, obesity, impaired glucose tolerance, high blood cholesterol, hyperglycemia, hyperinsulinemia, dyslipidemia and hyperlipidemia, or any other disease or disorder of the endocrine system.

As used herein, the term “cancer” or “tumor” refers to a disease caused by cells that exhibit uncontrolled and/or abnormal cellular proliferation.

Additional examples of diseases for which the likelihood can be estimated are provided in Example 2 of the Examples section that follows.

FIG. 1is a flowchart diagram of a method suitable for estimating a likelihood of developing a disease, according to various exemplary embodiments of the present invention.

The method can be embodied in many forms. For example, it can be embodied in on a tangible medium such as a computer for performing the method steps. It can be embodied on a computer readable medium, comprising computer readable instructions for carrying out the method steps. In can also be embodied in electronic device having digital computer capabilities arranged to run the computer program on the tangible medium or execute the instruction on a computer readable medium.

Computer programs implementing the method of some embodiments of the present invention can commonly be distributed to users on a distribution medium such as, but not limited to, a floppy disk, a CD-ROM, a flash memory device. In some embodiments of the present invention computer programs implementing the method are distributed to users over a communication network such as the internet. From the distribution medium or communication network, the computer programs can be copied to a hard disk or a similar intermediate storage medium. The computer programs can be run by loading the computer instructions either from their distribution medium or their intermediate storage medium into the execution memory of the computer, configuring the computer to act in accordance with the method of this invention. All these operations are well-known to those skilled in the art of computer systems.

It is to be understood that, unless otherwise defined, the operations described hereinbelow can be executed either contemporaneously or sequentially in many combinations or orders of execution. Specifically, the ordering of the flowchart diagrams presented herein is not to be considered as limiting. For example, two or more operations, appearing in the following description or in the flowchart diagrams in a particular order, can be executed in a different order (e.g., a reverse order) or substantially contemporaneously. Additionally, several operations described below are optional and may not be executed.

Referring toFIG. 1, the method begins at10and optionally and preferably continues to 11 at which a set of gene sequences corresponding to the disease is obtained, and to 12 at which a DNA sequence of a subject is obtained.

The DNA sequence is optionally and preferably in digital form and can be received by the method from an external source, such as a memory medium or over a communication network.

In some embodiments, the DNA sequence is extracted, as known in the art, from isolated cells by laboratory techniques, such as, but not limited to, ligation-mediated PCR, degenerate oligonucleotide primer PCR, and multiple displacement amplification.

In some embodiments, the DNA is extracted by performing at least some of the following operations. Cell lysis procedure is executed to expose the DNA in the cell. This can be done, for example by chemical and/or physical techniques, including, without limitation, blending, grinding and/or sonication. The membrane lipids can then be removed, for example, by adding a detergent or surfactants, which may also serve in cell lysis. Proteins can be optionally removed, e.g., by adding a protease, and RNA can optionally be removed, e.g., by adding an RNase. Thereafter, a purification procedure can be applied to purify the DNA from detergents, proteins, salts and/or reagents used during the cell lysis. The procedure can include, for example, ethanol precipitation, e.g., by cold ethanol or isopropanol. Since DNA is insoluble in these alcohols, it aggregates together, giving a pellet upon centrifugation. Precipitation of DNA can optionally be improved by increasing the ionic strength, e.g., by adding sodium acetate. The procedure can additionally include phenol-chloroform extraction, wherein phenol denatures proteins in the sample. After centrifugation, denaturized proteins stay in organic phase while aqueous phase containing nucleic acid is mixed with the chloroform that removes phenol residues from solution. The procedure can additionally include minicolumn purification that relies on the fact that the nucleic acid may bind (adsorption) to the solid phase (silica or other) depending on the pH and the salt content of the buffer. The procedure can additionally include refinements in which a chelating agent is added to sequester divalent cations such as, but not limited to, Mg.sup.2+ and Ca.sup.2+, so as to prevent enzymes such as DNase and the like from degrading the DNA. The procedure can additionally include removal of cellular and histone proteins bound to the DNA. This can be done by adding a protease or by having precipitated the proteins with sodium or ammonium acetate, or extracted them with a phenol-chloroform mixture prior to the DNA-precipitation. The isolated DNA can thereafter be dissolved in slightly alkaline buffer, e.g., TE buffer, or in ultra-pure water. All these operations are well-known to those skilled in the art of DNA extraction.

The set of gene sequences is optionally and preferably obtained by accessing a database having a library of diseases which comprises a plurality of library entries, each library entry comprises a disease and a set of gene sequence that is associated with the disease. The number of genes in each set is preferably at least 1, at least 2, or at least 3, or at least 3, or at least 4, or at least 5, or at least 6, or at least 7, or at least 8, or at least 9, or at least 10, or more. The present embodiments contemplate a set which includes a single gene. A representative example of a database, which is not to be considered as limiting, is shown inFIG. 2, and a method suitable for constructing such a database is provided hereinunder.

As used herein, “gene sequence” refers to a nucleic acid sequence that undergoes transcription as the result of promoter activity. A gene may code for a particular protein or, alternatively, code for an RNA sequence that is of interest in itself, e.g. because it relates to the development of a disease. The term “gene” encompasses genes, gene variants as well as their mutations.

As used herein, “gene variant” refers to any alteration in the wild-type gene sequence, and includes variations that occur in coding and/or non-coding regions of the gene. Representative examples of variants include, without limitation, allelic variants, splice variants, derivative variants, substitution variants, deletion variants, and/or insertion variants or fusion polypeptides.

As used herein, “mutated gene” refers to a gene in which there is a change in the sequence of the gene, including, without limitation a base substitution, insertion, deletion, inversion, duplication and translocation. The region of the mutation in a mutated gene is not limited to a transcriptional region, but includes a regulatory region such as a promoter which is required for gene expression. In this regard, the mutation in a mutated gene does not require a functional change, although some embodiments do contemplate a functional change.

In some embodiments of the invention at least one of the genes in the set, e.g., all the genes in the set, is an oncogene. In some embodiments of the invention at least one of the genes in the set, e.g., all the genes in the set, is a tumor suppressor gene. In some embodiments of the present invention at least of the genes in the set is an oncogene and at least one of the genes in the set is a tumor suppressor gene. In some embodiments of the present invention each of the genes in the set is either an oncogene or a tumor suppressor gene.

As used herein, “an oncogene” refers to a gene encoding an expression product which transforms cells in culture or induces cancer in animals. The expression product of an oncogene causes a cell to inappropriately enter the cell cycle hence lead to unregulated proliferation. Most oncogenes require an additional step, such as mutations in other genes, or environmental factors, such as viral infection, to cause cancer.

As used herein, “an expression product” refers to mRNA or protein.

According to some embodiments of the invention, oncogenes are derived from normal cellular genes known as proto-oncogenes whose products participate in cellular growth-controlling pathways. Mutations that convert proto-oncogenes to oncogenes are typically dominant gain of function mutations.

Alternatively, oncogenes may be derived from tumor suppressor genes in which loss of function mutations rendered them into oncogenes, as further described hereinbelow.

As used herein, the term “gain of function” refers to an increase in the expression of the normal gene or the activity of an encoded protein. Exemplary mechanisms that can induce gain of function include, but are not limited to, point mutations in a proto-oncogene that result in a constitutively acting protein product; gene truncation, leading to loss of regulation, gene amplification of a DNA segment that includes a proto-oncogene, leading to overexpression of the encoded protein; and chromosomal translocation that brings a growth-regulatory gene under the control of a different promoter and that causes inappropriate expression of the gene.

According to some embodiments of the invention, the gain of function mutations are dominant mutations.

Exemplary oncogenes include, but are not limited to, positive-acting growth factors and their receptors, signal-transduction proteins, transcription factors, and cell-cycle control proteins.

In various exemplary embodiments of the invention at least one of the genes in the set, more preferably all the genes in the set, is an oncogene. In the representative and non-limiting example of the database shown inFIG. 2, the diseases are types of cancer and are shown at the right hand side ofFIG. 2, and the associated genes are oncogenes which are shown at the left hand side ofFIG. 2, where an association between a set of oncogenes and a disease is represented by an arrow. As shown, more than one disease is associated with each set of genes, but this need not necessarily be the case since in some embodiments of the present invention, a single disease can be associated with a single set of genes. Preferably, each disease of the database is associated with a single set of genes.

As used herein, “a tumor suppressor gene” refers to a gene encoding an expression product which inhibits the formation of a tumor. The normal function of a tumor suppressor gene is to inhibit cell proliferation, repair DNA mistakes, or control apoptosis.

A mutation that results in a loss of function of a tumor suppressor gene can cause a cell to inappropriately enter the cell cycle hence lead to unregulated proliferation. Thus, a mutated tumor suppression gene expression product is able to transform cells in culture or to induce cancer in animals.

As used herein, the term “loss of function” refers to a decrease in the expression of the normal gene or the activity of the encoded protein.

According to some embodiments of the invention, the loss of function mutations are recessive mutations meaning as long as the cell contains one functional copy of a given tumor suppressor gene, that gene suffices to control cell proliferation thus can inhibit the formation of tumors. Typically both alleles of a tumor suppressor gene must be altered for transformation to occur.

According to other embodiments of the invention, a mutation in a tumor suppressive gene acts as dominant negative, for example certain mutations in the p53 gene can prevent the function of normal protein from the un-mutated allele.

Exemplary genetic alterations that can induce loss of function include, but not limited to, point mutations, gene deletions and epigenetic alterations leading to gene silencing or production of a nonfunctional protein. Loss of heterozygosity (LOH) of the normal allele in a somatic cell that contains one mutant and one normal allele of a tumor-suppressor gene can occur for example by mitotic recombination or chromosome missegregation.

Exemplary expression products of tumor suppressor genes include, but not limited to, intracellular proteins that regulate or inhibit progression through a specific stage of the cell cycle; receptors for secreted hormones that function to inhibit cell proliferation; checkpoint-control proteins that arrest the cell cycle if DNA is damaged or chromosomes are abnormal; proteins that promote apoptosis; and enzymes that participate in DNA repair.

The method continues to 13 at which, for each gene sequence of the set, the DNA sequence is searched for reoccurrences of the gene sequence, and to 14 at which the average reoccurrence distance trbetween adjacent reoccurrences of the gene sequence is calculated.

In some embodiments of the invention, the starting position for the search over the DNA sequence is selected wherein the search 13 is initiated at the selected starting position. Optionally and preferably the selection of starting position is selected randomly (e.g., using a uniform distribution or any other distribution). In some embodiments, a plurality (e.g., at least 2, or at least 4 or at least 8 or at least 16 or at least 32 or at least 64 or at least 128 or at least 256 or at least 512 or at least 1024) of starting positions is selected, optionally and preferably randomly. In these embodiments, the search 13 is initiated a respective plurality of times, each time at a different selected starting position.

It is not necessary for the search to traverse the entire length of the DNA sequence, although such an embodiment is also contemplated. In some embodiments, the searching is terminated when a predetermined number of reoccurrences is found. The predetermined number of reoccurrences can be at least a reoccurrence or at least 5 reoccurrences or at least 10 reoccurrences or at least 20 reoccurrences or at least 40 reoccurrences or at least 80 reoccurrences. It is to be understood that a single reoccurrence corresponds to two occurrences of the same gene. Use of a single reoccurrence is particularly useful when a plurality of starting positions is selected.

The number of all possible sets of genes is 2′, where n is the total number genes (approximately 23,000 genes if all human genes are considered, and many tens of genes if only oncogenes and/or tumor suppressor genes are considered). The number of base pairs in a DNA sequence of humans is about 3.2 billion. It is appreciated that the computation power that is required to calculate the probability of finding all possible sets of genes in the DNA sequence is extremely high. The present inventor found that the computation power can be significantly reduced by considering only a set of genes from the library, by calculating the average distance between adjacent reoccurrences of gene sequences of the set and optionally by terminating the search after a predetermined number of reoccurrences is found. The use of average distance is based on a mathematical lemma known as the Sadeh Lemma, which was discovered by the present inventor and was published in Sadeh, 1996, Optimal Data Compression Algorithm, Computers and Mathematics with Applications, 57-72.

The Sadeh Lemma relates to the calculation of the probabilities to find sets of strings of different lengths and types in long sequences. Following is a description of Sadeh Lemma.

v be a finite-valued infinite stationary sequence;

V be an alphabet upon which v is defined;

vijbe a sample sequence between positions i and j in the sequence v;

B be any set of strings of length l taken from the space of all possible strings of length1, defined on the alphabet V; BCVl.sup.l such that the probability of B, denoted Pr(B), is positive; and

Ynbe a string of length1, starting at the position n, Yn=vnn+l-l.

Two strings, Ynand Ymare approximately matched with respect to B if Yn∈B and Ym∈B.

The conditional probability that an approximate match with respect to B will have its first occurrence at step k, is given by:

The average reoccurrence distance subject to the set B can be defined as:

An event A in which members of B are found can be written as:

In probabilistic notation, the general form of Sadeh Lemma is:

In various exemplary embodiments of the invention, the DNA sequence is considered as a stationary ergodic process so that

A proof of Sadeh Lemma is provided in Example 1 of the Examples section that follows.

Referring now again toFIG. 1, the method continues to 15 at which the likelihood of the subject to develop the disease is estimated based on the calculated distances. In various exemplary embodiments of the invention Sadeh Lemma is employed. The set of gene sequences obtained at11(e.g., from a respective library entry) enacts the set of strings B in Sadeh Lemma, and the average reoccurrence distances trcalculated at14enacts the average reoccurrence distance μ(B) in Sadeh Lemma. Thus, under the consideration that the DNA sequence is a stationary ergodic process, and using Sadeh Lemma, the probability of finding the set of gene sequences in the DNA sequence can be calculated as 1/f(tr), where f is a function of the average reoccurrence distances tr. In various exemplary embodiments of the invention f(tr) is a set-average distance that is calculated over the set. The set-average can be an arithmetic average, a weighted average, a geometric average, or any other type of average that is calculated over the set. For example, denoting the average reoccurrence distance of the ith gene sequence of the set by tr,i, f(tr) can be calculated as (1/N)Σi(tr,i), where N is the number of gene sequences in the set and the summation is over i=1, . . . , N.

Once the probability of finding the set of gene sequences in the DNA sequence is found, the likelihood of the subject to develop the disease is calculated using the probability. The likelihood can be provided in a binary manner, or in any other discrete or continuous manner. For example, when the likelihood is defined in a binary manner (i.e., there are only two different likelihood levels) the likelihood of the subject to develop the disease can be “low” and “high” wherein “low” means that it is not likely for the subject to develop the disease, and “high” means that it is likely for the subject to develop the disease. As will be appreciated by one ordinarily skilled in the art, “low” and “high” can be represented numerically by, e.g., “0” and “1”, respectively. The likelihood can be defined in a binary manner using a single probability threshold. For example, when the probability of finding the set of gene sequences in the DNA sequence is above the probability threshold, the likelihood can be set to “high” and when the probability of finding the set of gene sequences in the DNA sequence equals or is less than the probability threshold, the likelihood can be set to “low.”

Alternatively, more than two different likelihood levels can be defined and be assigned with a discrete or continuous numerical value. A discrete numerical value of the likelihood can be defined in terms of several predetermined thresholds. A continuous numerical value can be defined in terms of the calculated probability itself. For example, the likelihood can be the calculated probability or some normalized representation thereof (for example, the calculated probability multiplied by a constant factor, e.g., 100).

In some embodiments of the present invention the rate of matches that are found along the DNA sequence is extracted and correlated to the expected development stage of the disease, and in some embodiments of the present invention the accuracy of the matches as compared to the gene sequence is calculated and correlated to the expected development stage of the disease. The accuracy can be calculated in terms of the similarity level (e.g., number of insertions, deletions and/or mutations) between the respective fragment of the DNA sequence and the gene sequence.

The method ends at 16.

Reference is now made toFIG. 3which is a flowchart diagram describing a method suitable for constructing a database of disease related genes, according to some embodiments of the present invention. In various exemplary embodiments of the invention an intermediate or end result of this method is the creation of a database, which can then be used as reference for later individual estimations on subjects. The method is particularly useful for constructing a database that can be subsequently be accessed for the purpose of estimating a likelihood of developing a disease, e.g., by employing one or more of the operations of method10described above.

The method begins at 30 and continues to 31 at which a DNA sequence of a subject identified as having a disease, and a set of gene sequences associated with the DNA sequence are obtained. The disease can be any of the diseases described herein. The subject from whom the DNA sequence and associated gene sequences are obtained at 31 is referred to herein as a target subject, the DNA sequence obtained at 31 is referred to herein as the target DNA, and the gene sequences associated with the target DNA sequence are referred to herein as target gene sequences. The target DNA sequence and the target gene sequences are optionally and preferably obtained from a subject that belongs to a target group for researching the particular disease. In these embodiments, the method is optionally and preferably repeated for each of at least a few subjects of the target group.

In some embodiments of the present invention the target genes are obtained together with a list of positions along the DNA at which these genes are found. This can be obtained as an input to the method from an external source, such as a memory medium or over a communication network. In some embodiments, the DNA sequence, gene sequences and respective positions are extracted by laboratory techniques as known in the art. For example, a whole or a partial genome sequencing can be employed. Typically, there is more than one instance of a particular gene in the DNA, and for such a gene, the obtained data preferably include several positions along the DNA, at least one position (e.g., starting position) for each gene.

In an optional operation, the method continues to 32 at which a DNA sequence of a subject identified as not having the disease (preferably a subject that is identified as healthy) is obtained. The subject that does not have the disease (e.g., the healthy subject) is referred to herein as the control subject and the DNA sequence obtained at 32 is referred to herein as the control DNA sequence. Optionally, a set of gene sequences associated with the control DNA sequence is also obtained. The gene sequences associated with the control DNA sequence are referred to herein as control gene sequences. The control DNA sequence and optionally the control gene sequences are optionally and preferably obtained from a subject that belongs to a control group of subject, each being a healthy subject or at least identified as not having the particular disease.

In embodiments in which control gene sequences are obtained, the control genes are optionally obtained together with a list of positions along the control DNA at which these genes are found. This can be obtained as an input to the method from an external source, such as a memory medium or over a communication network. In some embodiments, the control DNA sequence, control gene sequences and respective positions are extracted by laboratory techniques as known in the art. For example, a whole or a partial genome sequencing can be employed. Typically, there is more than one instance of a particular gene in the DNA, and for such a gene, the obtained data preferably include several positions along the DNA, at least one position (e.g., starting position) for each gene.

It is to be understood that once the initial database entry is formed for a specific disease, data (e.g., DNA sequences and gene sequences) may be repeatedly added to improve the accuracy of the database. Further, the operations described herein are optionally and preferably repeated for each of a plurality of diseases, to form a database that includes at least one entry for each of the diseases.

In various exemplary embodiments of the invention the method continues to 33 at which an average reoccurrence distance t.sub.r between adjacent occurrences of a target gene in the DNA is calculated. Operation33is performed for the target DNA sequence and optionally also for the control DNA sequence. The calculation is preferably executed for each of at least a few of the target genes. In some embodiments of the present invention the calculation is also performed for each of at least a few of the control genes.

The method continues to 34 at which, for at least one subset of gene sequences, a correlation between the subset and the disease is estimated, based, at least in part, on the average reoccurrence distances of the genes in the subset. At 35, the subset of gene sequences, the disease and optionally the correlation are recorded to make a database entry.

The correlation can be estimated by employing Sadeh Lemma. Specifically, the method can use Sadeh Lemma for assigning a probability value to the relation between the target DNA sequence and the subset of gene sequences. For example, under a consideration that the target DNA sequence is a stationary ergodic process, and using Sadeh Lemma, the relation between the target DNA sequence and the subset of gene sequences can be associated with a probability value which equals 1/f(tr), where f is a function of the average reoccurrence distances tr, as further detailed hereinabove.

Once the probability value is assigned to the relation, the correlation to the disease can be estimated based on the assigned value. For example, when the assigned value is high (e.g., above a predetermined threshold) the method can estimate that there is a high correlation between the subset and the disease, and when the assigned value is low (e.g., equal or less that the predetermined threshold) the method can estimate that there is no or low correlation between the subset and the disease. Non binary correlations can be provided by using a set of probability thresholds so the correlation can be selected from a set of discrete correlation descriptors, a different descriptor for each interval generated by the probability thresholds. Non binary and continuous correlations can be provided using the value of the assigned probability or some normalized representation thereof (for example, the calculated probability multiplied by a constant factor, e.g., 100).

In various exemplary embodiments of the invention the method also assigns, preferably using Sadeh Lemma, a probability value to the relation between the control DNA sequence and the subset of target gene sequences. Preferably, the same procedure for calculating the probability is employed for both the target DNA and the control DNA. Thus, the present embodiments assign a pair of probability values to each of the subset of target genes. One probability value, denoted P.sub.target, describing the relation of the subset to the target DNA and anther one probability value, denoted Ptarget, describing the relation of the subset to the control DNA. In these embodiments, the two probability values Ptargetand Pcontrolare compared and the estimation of the correlation to the disease is also based on the comparison. To this end, a set of criteria can be defined for estimating the correlation. The criteria can be defined such that subsets that are more likely to occur in the target DNA than in the control DNA have higher correlation to the disease, and subsets that have equal likelihood to occur both in the target DNA and in the control DNA have low or no correlation to the disease.

As representative examples, Ptargetis larger than a predetermined threshold and Pcontrolequals or is less than the predetermined threshold, then the method can estimates high (e.g., above a predetermined threshold) the method can estimate that there is a high correlation between the subset and the disease. If P.sub.control approximately equals P.sub.target (e.g., when the absolute value |Pcontrol−Ptarget| is less than a predetermined threshold) the method can estimate that there is no or low correlation between the subset and the disease.

Typically, but not necessarily, the method is executed for group of subjects (e.g., a target group and a control group as further detailed hereinabove) and the method calculates probability values for the particular subset of target genes for several subjects of the groups. In these embodiments, a statistical analysis is optionally and preferably applied to the calculated probabilities to determine the correlation of the particular subset to the disease. The analysis can be applied separately to the target group, e.g., to provide a target group probability value that represents the confidence level of P.sub.target, and separately to the control group, e.g., to provide a control group probability value that represents the confidence level of p.sub.control. Then, a set of criteria can be applied to the target and control group probabilities, as further detailed hereinabove.

When a set of control gene sequences is obtained at32, this set can also be used for determining the correlation. For example, any of the procedures described above can be similarly executed, but for subsets of control gene sequences, and a supplementary set of criteria can be defined to estimate the correlation of the subset of target genes to the disease. Specifically, when the relation between the control DNA and a particular subset of control genes is assigned with a high probability value, subsets of target genes that are similar to this particular subset of control genes can be declared as having low correlation to the disease.

The method ends at36.

According to some embodiments of the present invention there is provided a system for estimating a likelihood of developing a disease. The system comprises a data processor, which is configured for obtaining from a database a set of gene sequences corresponding to the disease, obtaining a DNA sequence of a subject, searching over the DNA sequence for reoccurrences of gene sequences, calculating an average reoccurrence distance between adjacent reoccurrences, and estimating the likelihood of the subject to develop the disease, based on the calculated distances.

According to some embodiments of the present invention there is provided a system for constructing a database of disease related genes. The system comprises a data processor, which is configured for obtaining a DNA sequence of a subject identified as having a disease, and a set of gene sequences associated with the DNA sequence, calculating, for each of at least a few gene sequences in the set, an average reoccurrence distance between adjacent occurrences of the gene in the DNA, and determining, for at least one subset of gene sequences, a correlation between the subset and the disease, based, at least in part, on average reoccurrence distances of genes in the subset.

As used herein the term “about” refers to .+−0.10%.

The term “consisting of” means “including and limited to”.

EXAMPLES

A Proof of Sadeh Lemma

The event A is sliced as follows:

where + denotes the disjoint union. Firstly, it will be shown that:

In an ergodic process, the event occurs for any infinite-length time period. Taking the general and non-ergodic case into consideration, if the event A+occurs, then there is the smallest j≥0, such that Yj∈B, and therefore,

However, because the sequence {Yn} is stationary, the summand does not depend on j, and therefore vanishes.

If the two events A+and A−occur, there is a smallest j≥0, such that Y−k∈B, and the smallest k>0, such that Y−k∈B. Thus,

from the stationarity of Yn.

For stationary ergodic sources, one has:

and the Lemma has been proven.

The exact matching of a single string in a stationary and ergodic process, is extended according to some embodiments of the present invention to a more general case of matching a certain member of a specific set of strings in any stationary process, including a non-ergodic process.

The Present inventor found that even though the set of strings is defined of equal length, it can be extended to a set of strings of different lengths. The longest string in the set can be chosen, and for all other members of the set, the strings can be padded with arbitrary letters over the alphabet to provide strings with equal lengths.

The present disclosed subject matter has additional applications outside of those disclosed above for genetics, and disease analysis, and is used with Big Data analytics for various fields such as, quality assurance, event probabilities, statistical process control (SPC), finance, e-commerce, insurance and additional bio-informatics applications. The method utilizes “Big Data” analysis to rapidly and accurately calculate the probabilities of certain “TYPES”, which include, for example sets of objects, traits, events, and the like. For example, a “type” is a set of words characterized by traits, e.g., a set or singular, based in text, images, audio and video, which may be may defined by the Boolean operators AND or OR.

“Big Data”, as used herein includes data sets that are so large or complex that traditional data processing applications are inadequate. As a result, Big Data works with specialized computers and computing devices, in order to provide the analysis, capture, data curation, search, sharing, storage, transfer, visualization, querying and information privacy, associated with “Big Data.” “Big Data”, as used herein additionally refers to the use of predictive analytics, user behavior analytics, or certain other advanced data analytics methods that extract value from data, and seldom to a particular size of data set. By performing a big data analysis, the method of the present invention is performed on computer processors in real time, and is employed with processes such as streaming Big Data. By performing the disclosed processes in real time, on Big Data, the a computer processor is the only way in which such large amounts of data can be handled, in any reasonable amount of time, such that should there be a need to issue an alert based on the result, the alert can be issued in real time, contemporaneous with the “Big Data” analysis.

Processors suitable for processing the disclosed “Big Data” include, for example, AMD EPYC™ 7002 Series Processors, linked to storage/memory, which provides instructions to the processor for performing the big data operations of the disclosed subject matter.

The disclosed subject matter uses “Big Data” and Big Data Analysis to solve a specific problem of working with large volumes of records (for example in arrays), data strings and the like, totaling well over 10,000. The process uses computerized Big Data analytics, with computerized processors linked to memory, to hold all of the records and data strings to make them available for analysis. The data processor is such that it is programmed to isolate various series of records, data strings and the like, within the arrays, data strings and the like, so that not all of the 10,000 plus records or data strings need to be analyzed, but rather, certain consecutive records, data strings, and the like, from which a result of a probability or likelihood of an event, occurrence of a trait or characteristic, or the like is obtained, fast and accurately, and in real time. From this result, various actions may be taken by computers, machines and the like, automatically.

The disclosed subject matter provides for Statistical Process Control (SPC), which is a method of quality control, which employs statistical methods to monitor and control a process. This helps to ensure that the process operates efficiently, producing more specification-conforming products with less waste (rework or scrap). SPC can be applied to any process where the “conforming product” (product meeting specifications) output can be measured. Key tools used in SPC include run charts, control charts, a focus on continuous improvement, and the design of experiments. An example of a process where SPC is applied is manufacturing lines.

SPC must be practiced in two phases. The first phase is the initial establishment of the process, and the second phase is the regular production use of the process. In the second phase, a decision of the period to be examined must be made, depending upon the change in5M&E conditions (Man, Machine, Material, Method, Movement, Environment) and wear rate of parts used in the manufacturing process (machine parts, jigs, and fixtures).

An advantage of SPC over other methods of quality control, such as “inspection”, is that it emphasizes early detection and prevention of problems, rather than the correction of problems after they have occurred.

In addition to reducing waste, SPC can lead to a reduction in the time required to produce the product. SPC makes it less likely the finished product will need to be reworked or scrapped.

The Lemma on the Probability of a Set of Strings in a Long Sequence

The present disclosed subject matter applies the Kac-Sadeh Lemma to establish probabilities based on long strings of data, where the starting point for the evaluation of each data string is selected in accordance with Big Data analysis. This is followed by a calculation of the average distance between repeating various members in the data string, based on the first occurrence of the specific sequence after the selected starting point. The average first reoccurrence distance of a sequence can now be calculated rapidly, to predict a probability of the event (condition).

The lemma provides a solid background on calculating the probabilities of sets of strings of different lengths and types in long sequences, and therefore it has a wider range of possible applications in different scientific branches. In order to understand this lemma, consider the following (which has also been described above):v—is a finite-valued infinite stationary sequence.V—the alphabet upon which v is defined.vij—is a sample sequence between positions i and j in the sequence v.B—is any set of strings of length l taken from the space of all possible strings of length l, defined on the alphabet V; BCVlsuch that Pr(B)>0.Yn—is a string of length l, starting at the position n, Yn=vnn+l−1, therefore we can state that two strings, Y, and Ym, are approximately matched with respect to B if Yn∈B, Ym∈B.

The conditional probability that an approximate match with respect to B will have its first occurrence at step k, is given by:

The average reoccurrence distance subject to the set B is defined by:

The event is such that for the realizations of v, members of B are found as:

1. The Lemma in Probabilistic Notation

The general form of the Lemma is given as:

For a stationary ergodic process (a special case), there is the relationship:

Proof of the Lemma (also detailed in Example 1)

The event A is sliced as follows:

where “+” denotes the disjoint union. It is now shown that;

From intuitive suggestion, it is obvious that during an ergodic process, in any infinite-length time slot, the event must occur. Taking the general and non-ergodic case into consideration, if the event A+occurs, then there is the smallest

j≥0, such that Yj∈B, and therefore,

However, because the sequence {Yn} is stationary, the summand does not depend on j, and must therefore vanish. Similarly,

If the two events A+and A−occur, there must be the smallest j≥0, such that Yj∈B, and the smallest k>0, such that Y−k∈B. Thus,

from the stationarity of Yn.

In particular, for stationary ergodic sources, there is:

Equation PE is the Equation which defines the probability of an Event.

The exact matching of a single string in a stationary and ergodic process, is extended to a more general case of matching a certain member of a specific set of strings, which is a “type” denoted by “B”, in any stationary process, including a non-ergodic process.

It should be emphasized that despite the set of strings being defined of equal length, it can be easily extended to a set of strings of different length. The longest string in the set has to be chosen, and for all other members of the set, we define such longer strings with arbitrary (“don't care”) letters over the alphabet (any letter over the given alphabet would be accepted). In this way, all the strings of the set are equalized in length, and then the same algorithm can be applied to them.

The aforementioned additional applications of the present invention are based on the Kac-Sadeh Lemma, which governs a relationship between a group of data strings and an average first reoccurrence distance, from a starting position. The starting position for each data string is, for example, randomly or arbitrarily chosen (selected), either manually or by computer programs. The average first reoccurrence distance can be calculated rapidly to predict reoccurrences of an object. More particularly, the Kac-Sadeh Lemma is based on the probability of a set of strings in a long sequence, which is useful to calculate the probabilities of those particular sets of words characterizing the “Types”, by searching the set members in the Data, and calculating the average distance of first appearance of those members in the set in the Data sequence. It can be done only from certain randomly chosen positions in the Big Data. It is sufficient to find only a few such “distances”. Therefore, high speed and high accuracy is obtained in real time.

In this application of the Kac-Sadeh Lemma, a probabilistic paradigm is created, which involves mappings between subsets of “words” to risk types with a high probability. That is, a probability of a subset of words is highly correlated with the probability of predicting risk event type. This relationship is expresses as follows:

P(B) is the probability of the risk event—the “Type” B;

μ(B) is the average first reoccurrence distance for the set B; and,

the Set B is, for example, defined as:

B is a set of all items which can be defined by traits, with the traits operable by the Boolean operator AND (Boolean operator), or the Boolean Operator OR, or a list of items.

A “type” can be any set of strings that are predefined. For example, the Set B is a set of strings.

In this case, the Big Data is a data structure of is a set of strings of linear sequential data, e.g., binary ones and zeros.

An example of a set, such as Set B, is a set of strings. The database is linear, or a linear sequential data structure. This set of strings characterizes “Communication Failure”. For example, if a certain switch is “stuck at 0” there will be a long string of binary zeros (0). Arranged in a linear sequential data structure between a designated average first reoccurrence distance with binary zeros, four consecutive zeros or more. For example, let B be the set of the string with four consecutive binary zeros {0000}, as follows:

Where the average first reoccurrence (repetition) distance between 0000 and 0000 is the integer 31, for a probability of 1/31.

Based on this average first reoccurrence distance, a threshold for a communication failure is defined. For example, the threshold may be 1/16 a four bits (i.e., represented by the four binary zeros) have 16 possible combinations (assuming equal probability of 0 and 1 for each bit), such that, if the bit is chosen randomly, the probability is 1/16 for the string (of binary zeros) 0000.

With the string having a probability of 1/31, this is less than 1/16, so there is no need to issue an alert. The switch is not stuck at zero.

The first reoccurrence (repetition) distances of the four binary zeros are the integers of 5 and 6, for an average of 5.5, where: 1/5.5 is greater than the threshold 1/16, such that an alert should be issued, as something is suspicious.

As a result, it is possible to calculate, in real time, that in a long data string, there is a high probability of “stuck at zero”, of a certain switch in the network.

This computerized Big Data process discussed above, is shown as an example process for detecting a communication failure, as discussed above. The process is shown inFIG. 4, as a flow diagram. The process begins at the START block400, where Big Data is a data structure of is a set of strings of linear sequential data, e.g., binary ones and zeros. An example of a set, such as Set B, is a set of strings. The database is linear, or a linear sequential data structure. This set of strings characterizes a switch “stuck at zero”. For example, if a switch is “stuck at zero”, there will be a long string of binary zeros (0), for example four consecutive binary zeros.

A starting point for analyzing the linear set of strings, is the START block400. Also at block400, a threshold value for the communication failure is determined. From the discussion above, a value of 1/16 is selected as the threshold, since there are four bits (e.g., four binary zeros) with two possibilities each, of binary 0 and 1, for a total of 16 possible combinations.

At block402, the linear set of strings is analyzed for the average first reoccurrence distance between series of four binary zeros is developed, yielding a value (number) for the average first reoccurrence distance at block404. The average first reoccurrence distance is compared to the threshold value, at block406.

At block406, if the average first reoccurrence distance, translated into a probability (e.g., the inverse of the average first reoccurrence distance) is greater than threshold, an alert of the communication failure is issued, at block408. The process then moves to the END at block410. Alternately, at block406, if the average first reoccurrence distance, translated into a probability (e.g., the inverse of the average first reoccurrence distance) is less than threshold, the process continues as normal, moving to the END, at block410. Although the process has ended at block410, it may be repeated for as long as necessary.

This process can be adapted for statistical quality control by replacing the communication failure of “stuck at zero”, with “abnormal or defective product”. The process remains the same.

However, when applying the Kac-Sadeh Lemma to the probability of a set of strings in a long sequence, the Lemma is useful to calculate the probabilities of particular sets of words, by searching the set in the Data Streaming, and repeatedly calculating the average index of first appearance of those sets in the Streaming Data sequence.

Applying the same principles as disclosed for Case 1 above, the same algorithms can be applied to monitoring and controlling of on-line or off-line streaming of audio streams using Big Data. For example, an audio stream, here, a long linear data string or linear sequential data structure, which may be performing surveillance of a potential bank robbery may be analyzed by a listening device and/or a voice recognition device, linked to a processor, to detect and analyze sets of “Bad or Target Words” (programmed into the processor and/or voice recognition device), such as “bank”, “bomb”, “vault”, “guard”, “rob”, “hold-up”, etc., and related sounds phrases, and the like. If it is detected (by the listening device and/or a voice recognition device) and determined by the processor that a certain person is using these words with a high frequency, and the word distance between them, this is indicated as suspicious. The computer (processor) will issue, or cause issue of, an alert of these potential suspects, having the conversation under surveillance.

For example, based on the above, disclosed is a surveillance method. The surveillance method comprises: accessing a database stored on non-transitory computer readable medium, the database including an audio stream; selecting a set of one or more of words (the words including words, sounds, phrases, and the like); by an audio detector, detecting the words from the playing of the audio stream; and, by a processor, analyzing the distances between the detected words, and determining the probability of the likelihood of the event based on the distances between the words.

Application—Case 2 Quality Control of Products, Such as Automobile Engines

Case 2 presents a Big Data process for finding the probabilities of “types”, e.g., a subset of items in a Big Data set. The “Big Data” is a data structure of a long array of items, where each item is represented by a set of traits, also known as a record of traits.

The Set B

For example, the Set B may be a set of words associated with a “Risk Event”. The Set B may also be expressed as a set of items. Each item includes a finite number of traits. Each trait is, for example, text, numbers, graphics, video or audio.

For example,FIG. 5Ashows a long array of items, for example, an automobile engine. Each item represents an engine, and includes a line including traits of the particular engine. Records of Items are from Engine1through Engine n, where n is, for example 10,000 or greater, so as to require a big data analysis in real time to obtain and instantaneous result.

As this is a “Big Data” example, there would be at least 10,000 data strings, one data string for each engine, each engine numbered 1 through n, n being the last engine, but at least number 10,000 in a sequence, arranged in an array for a Big Data analysis. A starting point is selected, for example, the starting point being after the left side “. . . The data string characteristics, for each string (e.g., representing an engine) are selected, with the end of the analysis of the string represented by the right “ . . . ”. Taking the first data string for Engine1, the engine failure was caused by the characteristics of high temperature AND (Boolean operator) low oil pressure. With this being a cause of engine failure, the subsequent data strings are analyzed for these two characteristics, which occurred in Engines1and4. Accordingly, the distance is 4-1 or 3, meaning that these two characteristics are a strong probability of an engine failure, and vehicles with these two characteristics should be alerted. The next engine failure from high temperature AND oil pressure occurred in Engine9, for a distance of 9-4 or 5. Taking an average of3and5is 4.

Applying statistical quality control, another series of items (records) in the array, taken at an arbitrary starting point in the array, is subject to the same Big Data analysis which returned the average first reoccurrence distance, for example, the integer 4, above. Should the average first reoccurrence distance between items be less than the average first reoccurrence from the initial Big Data analysis, which is the integer 4, the items from these records of this subsequent Big Data analysis, would be removed from the production line.

For example, this is shown inFIG. 5B, which is the array ofFIG. 5Abut including records for Engine1000to Engine1006, which were randomly selected. The first reoccurrence distance, between record1000and1002is the integer 2, and the subsequent reoccurrence distance between record1002and record1005is the integer 3. Accordingly, the average first reoccurrence distance is 3+5+2+3/4 or the number 3.25, for records1000to1006. As a result, average first repeat distance is frequent, and the population of engines should be discarded.

Returning toFIG. 5A, and taking the first item/record for Engine1, the engine failure was caused by the characteristics of high temperature OR (Boolean operator) low oil pressure. With this being a cause of engine failure, the subsequent data strings are analyzed for these two characteristics, with the OR operator, leading to a detection at Engine4, and Engine7. As a result, the first reoccurrence distance is 4−1 or 3, and the subsequent first reoccurrence distance is 7−4 or 3, such that the average first reoccurrence distance is 3.

This computerized Big Data process discussed above, is shown as an example process of statistical quality control, such as a quality control process for widgets, and is shown in the flow diagram ofFIG. 5C-1.

The process begins at the START block500, where an array is developed of records, for example over 10,000 records, shown inFIG. 5C-2. At block502, a starting point for the records is selected, a “Type”, e.g., a set of traits or the like, is determined, for example, discoloration AND (Boolean) surface imperfection, from the traits, discoloration (Dis. Color), cracks, heat damage, surface imperfection (Surf. Imperf.), thin spots, and warping (warp.). An average first reoccurrence distance between records indicative of the “Type” is established, at block504, which, for example is the integer 3, based on reoccurrence distances of the integer 3, between Record1and Record4, and Record4and Record9, for an average first reoccurrence distance of 4.

A second starting point for subsequent records, for example, Record1000is selected at block506. The records from Record1000, for example, Records1000to1006are analyzed for an average first reoccurrence distance based on the same “Types”, at block508. At block508, the average first reoccurrence distance is calculated, by adding the subsequent reoccurrence values to the previous reoccurrence values, for example, 3+5+2+3, where 3 and 5 were from records 1-10, while 2 and 3 were from records1000to1006, and taking the average, which is 13/4 or 3.25. A decision is made as to keeping or discarding the population of widgets, based on the average first reoccurrence distance, at block510.

From block510, the process moves to block512, where it ends, but may be repeated for as long as desired.

The Big Data Algorithms, which are based on the Kac-Sadeh Lemma are usable to spot business trends, prevent diseases, combat crime, perform e-Science work, including meteorology, genomics, connectomics, complex physics simulations, biology and environmental research, quality assurance, event probabilities, statistical process control (SPC), and other applications. Assuming large data-sets in areas including Internet search, fintech, urban informatics, and business informatics, various probabilities for events can be determined.

Machine Learning BIG DATA

Machine learning (ML) is a field of computer science that gives computer systems the ability to “learn” (i.e., progressively improve performance on a specific task) with data, without being explicitly programmed.

Machine learning in Big Data is the ability to “learn” the Big Data without being explicitly programmed and tested over all the data.

There are five dimensions to big data. These five dimensions include: Volume, Variety, Velocity and the recently added Veracity and Value.

It is important to classify the Big Data, as it is desired to find the Big Data “Type”, without having to scan entire strings of Big Data. “Types” are defined as: “good” “bad” “Risk”, “Disaster”, etc. Each “Type” is characterized by set of strings: words/video/audio in cases such as: business trends, diseases, combat crime. The algorithms for analyzing Big Data can be generalized to: spot business trends, prevent diseases, combat crime, and the like.

The disclosed subject matter uses two example approaches to utilize big data applications for various technical fields. One approach is a probabilistic approach associated with risk, and another probabilistic approach for communication failures.

The Probabilistic Approach For Risk

This example approach is a generalized study of a probabilistic paradigm where there are mappings between subsets of “risk words” to risk types with a high probability. That is, a probability of a subset of words is correlated with the probability of predicting a risk event type.

However, the Lemma on the probability of a set of strings in a long sequence, can be useful to calculate the probabilities of those particular sets of words, by searching the set in the Big Data and repeatedly calculating the average index of first appearance of those sets in the Big Data sequence.

The Big Data sequence is considered to be a long stationary ergodic process with finite value alphabet.

Initially, there is a problem in that determining different probabilities for each subset of words in a particular Big Data sequence is almost impossible because of the extremely high computational burden which is required. The number of all possible subsets is 2n, where n is the number of words.

From this, the application of the Lemma in this case is obvious. This Lemma provides a relatively simple way for evaluation of the probability of a subset of words, making use of a partial search for the first repetition from a few randomly chosen starting points, in a particular Big Data sequence of interest. Finding the average first repetition (reoccurrence) distance, tr, for the occurrence of a desired match implies that the probability of the “TYPE”, where the TYPE is a finite set of items words, patterns, video, audio, and the like, formed of traits, subject to the Boolean operator AND or OR to define the set, for example, as set of traits, subject to equations such as:

Case 1—the Algorithm for Finding the Probabilities of Subsets of Strings of Big Data

The Lemma is applied to an algorithm that efficiently calculates the probabilities of subsets of strings or “Types” in a long sequence of bits, which is the Big Data.

Initially, it is assumed that Big Data can be considered as ergodic and stationary process.

The basic algorithm is the following:1. Given are a subset of strings (Type) and a Big Data long sequence.2. Given the Big Data sequence, find the first repetition of the Type from a few randomly chosen starting points on the Big Data sequence. Store the distances of first repetition.3. Find the average first repetition “distance” tr, (the reoccurrence of a member of the “subset”), from the big data sequence (long sequence).4. Calculate the probability of the Type.

Case 2—the Algorithm for Finding the Probabilities of Subsets of Items in a Long Array of Items. The Long Array of Items is the Big Data.

The Lemma is applied to an algorithm that efficiently calculates the probabilities of subsets of strings in a long array of items, which is the Big Data.

Initially, it is assumed that Big Data can be considered as ergodic and stationary process. The basic algorithm is the following:1. Given are a subset of items (Type) and a Big Data, which is the long array of items.2. Given the Big Data array, find the first repetition of the Type(e.g., set of items, each item represented by a set of traits (each item ids a record of traits) from a few randomly chosen starting points on the Big Data array. Store the distances of first repetition.3. Find the average first repetition “distance” tr, (the reoccurrence of a member of the “subset”), from the array of items.4. Calculate the probability of the Type:

Solving the Problems of “Characterizing” and “Analyzing”

Solving the problem involves two main goals, characterization and analysis. The characterization and analysis are typically performed using Big Data analytics.

“Characterizing” involves a fast and accurate decision about an unknown population. For example, given unknown Big Data, find the probabilities of “types” that characterize it.

Fast Calculations of Probabilities of Types in Big Data

Initially, it is assumed that there are a few Types are characterized subsets of words (alphabetical words or video or audio . . . ).

Attention is directed toFIG. 6, which shows a model of the “Characterizing”.

Big Data is a long SEQUENCE of DATA

P(Bi) . . . P(Bk) the probabilities of the TYPES occurrence in the Big Data Sequence where TYPE is a collection of FEATURES.

Look at the repeating sequences that belong to a TYPE.

Calculate the probabilities for all TYPES based on the Big Data Sequences

The entire Big Data sequence need not be scanned, it just needs to be sampled to find the first repetition distance.

For Case 1, the types are represented by a set of binary words, such as the word comprising four consecutive binary zeros. For Case 2, each “Type” is a set of words, defined by traits, patterns video, audio and the like.

For example, if a certain switch is “stuck at 0” there will be a long string of binary zeros (0). Arranged in a linear sequential data structure between a designated average first reoccurrence distance with binary zeros, four consecutive zeros. For example, let B be the set of the string with four consecutive binary zeros {0000}, as follows:

Where the first average (first) repetition distance between 0000 and 0000 is the integer 31, for a probability of 1/31.

Based on this average first reoccurrence distance, a threshold for a communication failure is defined. For example, the threshold may be 1/16 a four bits (i.e., represented by the four binary zeros) have 16 possible combinations (assuming equal probability of 0 and 1 for each bit), such that, if the bit is chosen randomly, the probability is 1/16 for the string (of binary zeros) 0000.

With the string above 1/31 is less than 1/16, so there is no need to issue an alert. The switch is not stuck at zero.

Now, for the long string: . . . 000010000110000101 . . . , first reoccurrence (repetition) distances of the four binary zeros are the integers of 5 and 6, for an average of 5.5, where: 1/5.5 is greater than the threshold 1/16, such that an alert should be issued, as something is suspicious.

As a result, it is possible to calculate, in real time, that in a long data string, there is a high probability of “stuck at zero”, of a certain switch in the network.

For example, if there is Big Data about automobile engine failures, with the Big Data being an array of items, each “Type” is a set of items, e.g., engines, with a specific pattern defined by traits. By looking for first repeating occurrences of this pattern, in a Big Data analysis, the probability of engine failure is determined. The first reoccurrence of the “Types” is searched in only a few sections of the “Big Data” array, and can obtain the probability of each Type in the “Big Data” array without searching the entire database, e.g., the entire “Big Data” array.

Attention is directed toFIG. 5Awhich shows a long array of records, where there are data items representing each engine in a population of engines. As this is a “Big Data” example, there would be at least 10,000 data strings, one data string for each engine, each engine numbered 1 through n, n being the last engine, but at least number 10,000 in a sequence, arranged in an array for a Big Data analysis. A starting point is selected, for example, the starting point being after the left side “ . . . ”. The data string characteristics, for each string (e.g., representing an engine) are selected, with the end of the analysis of the string represented by the right side “ . . . ”.

Taking the first data string for Engine1, the engine failure was caused by the characteristics of high temperature AND (Boolean operator) low oil pressure. With this being a cause of engine failure, the subsequent data strings are analyzed for these two characteristics, which occurred in Engine3. Accordingly, the distance is 4-1 or 3, meaning that these two characteristics are a strong probability of an engine failure, and vehicles with these two characteristics should be alerted. The next engine failure from high temperature AND oil pressure occurred in Engine9, for a distance of 9-4 or 5. Taking an average of 3 and 5 is 4. Accordingly, there is a 25 percent chance of an engine failure should there be high temperature and oil pressure drops, so if this occurs in a vehicle, an alert will be issued to the vehicle, vehicle owner, or other party associated with the vehicle.

Staying withFIG. 5A, and taking the first data string for Engine1, the engine failure was caused by the characteristics of high temperature OR (Boolean operator) low oil pressure. With this being a cause of engine failure, the subsequent data strings are analyzed for these two characteristics, with the OR operator, leading to a detection at Engine4, and Engine7. As a result, the first reoccurrence distance is 4−1 or 3, and the second reoccurrence distance is 7−4 or 3, such that the first average reoccurrence distance is 3.

Analyzing

“Analyzing” involves studying the nature of Big Data with a known common trait/attribute or property. For example, what is the most likely trait associated as a cause or reason for a particular event, such as an abnormal event, for example, a switch being stuck or an engine failure. Analyze the Big Data so as to develop at least one common property for the abnormal event. Look at the “Types” and determine the most likely type that is associated with “abnormal” Big Data, when compared to corresponding to “normal” Big Data. This analyzing allows for fast and accurately finding the most likely “type” of a particular item of Big Data.

Find the Likeliest SET that Best Characterize a Specific Known Big Data

Attention is directed toFIG. 7, which shows a model of the “Analyzing”.

For Example: Given 2 Big Data sets:

“Big Data 2”—Population of Abnormal

Change the SET B such that the HIGHEST Probability P(B) is obtaining for “Big Data 2 relative to Big Data 1.

Find B with the highest P(B) on “Big Data 2—compare to Big Data 1

Given Big Data about communication failures a set of patterns in two separate data strings of binary ones and zeros is associated with a communication failure. One Big Data is normal while the other Big Data is abnormal. By searching iteratively on the types, a set of Big Data is found, with probabilities or frequencies which are significantly higher in the abnormal Big Data, than the normal Big Data, whereby it can be concluded that the particular type(s) is/are the reason for the abnormality.

As an example, there are two Big Data strings (Big Data sets) for “communications”, 1) Communication Failures, and, 2) Normal Communications. The objective is to find the likelihood of the “type”, when compared to the normal, that is associated with the “failure” (e.g., the condition for which the probability is desired). As a starting point, there are communication failures, but, the reason for the failure is unknown and it needs to be determined or found.

Patterns in each of the Big Data strings are analyzed. When one pattern is much more prevalent in one data string than the other data string, for example, there are a large number of four consecutive binary zeros in the “communication failure” string, it may be concluded that this is the pattern, which caused the communication failure. Accordingly, this more frequent pattern in the communication failure data string is the reason for the communication failure.

For this case, the characterizing algorithm is used iteratively for each of the types in each array, normal, e.g., normal engines, and abnormal, failed engines. When the characterizing algorithm results in higher probabilities for abnormal than normal, it can be concluded that this “type” is the reason for the abnormality. By analyzing the two arrays, a fast conclusion, for example, in real time, can be made as to the reason for the abnormality.

For any product, an example being automobile engines, which have a particular failure, find a reason for the failure of the engine. Each “Type” is a set of patterns, in particular, a set of patterns associated with a particular failure. With a Big Data analysis, in real time, the “Type” of engine failure with the greatest likelihood can be found and verified against a normal population of automobile engines. This is known as the inverse, as based on something known, it is desired to know the reasons for the something known having occurred.

As an example, there are two Big Data bases (Big Data sets) for “automobile engines”, 1) Failed Engines, and, 2) Normal Engines. The objective is to find the likelihood of each “type”, when compared to the normal, that is associated with the “failure” (e.g., the condition for which the probability is desired). As a starting point, there are failed engines, but, the reason for the failure is unknown and it needs to be determined or found.

Patterns in the engines in both Big Data bases are analyzed. When one pattern is much more prevalent in one data set than the other data set, such as in the failed engine data set, it may be concluded that this is the pattern, which caused the failure in the failed engine data set. Accordingly, this more frequent pattern in the failed engine data set is the reason for the engine failure.

Big Data Inverse Problem

Assuming given a Big Data consisting of population that have had a specific “type” or trait, find the most likelihood set of strings of Types that are considered as characteristic of that particular “Type” type of trait (similar to the genetic disease in genomes as described above).

The basic algorithm is the following:1. Given a Big Data long sequence of a specific Type.2. Choose a subset of strings.3. Given the Big Data sequence, find the first repetition of the Subset from a few randomly chosen starting points on the Big Data sequence. Store the distances of first repetition.4. Find the average first repetition “distance” tr, (the reoccurrence of a member of the “subset”).5. Calculate the probability of the subset on that Big Data Sequence:

Pr{setofTYPE}=1Average(tr)6. Store the value of the probability for the chosen subset.7. Change the subset by replacing an element that is supposed to maximize the Probability.8. Repeat the procedure from step2to step6sufficiently enough times (n).9. The “maximum likelihood subset” is that one that maximizes the Probability.

The Algorithm for Finding the Probabilities of Subsets of Strings in a Long Big Data Sequence

The Lemma is applied to an algorithm that efficiently calculates the probabilities of subsets of strings in a long Big Data sequence.

It is assumed that Big Data can be considered as ergodic and stationary process. The basic algorithm is the following:1. Given are subset of strings that characterize Type of Data (Subset) and a Big Data long sequence.2. Given the Big Data sequence, find the first repetition of the Subset from a few randomly chosen starting points on the Big Data sequence. Store the distances of first repetition.1. Find the average first repetition “distance” tr, (the reoccurrence of a member of the “subset”).2. Calculate the probability of the subset:

Practical Aspects of the Disclosed Subject Matter

The disclosed subject matter is directed to a method of estimating a probability of at least one event in a population. The method comprises: accessing a database stored on non-transitory computer readable medium, the database including an array of items for the population, the items of an amount sufficient to be classified as Big Data; selecting a set of types possessed by at least one item of the array; randomly selecting a first item from the array to serve as a starting point, and inputting the starting point to a data processor, configured for processing Big Data; and, by a data processor programmed to perform Big Data operations on the array to obtain a probability for the set of types including, searching over the array, from the starting point, for at least one average first reoccurrence distance of the set of types, and, recording the value of the at least one average first reoccurrence distance; wherein the calculated average first reoccurrence distance defined a probability for the frequency of the set of types.

The method is such that it additionally comprises: rendering a decision as to the population based on the probability.

The method is such that the types include at least one of: words, traits, images, audio and video.

The method is such that the set of types includes at least one member.

The method is such that the set of types includes a plurality of members.

The method is such that the probability equals a reciprocal set average.

The method is such that it additionally comprises: randomly selecting at least one subsequent item to serve as a subsequent starting point, and inputting the starting point to a data processor, configured for processing Big Data; by the data processor, performing Big Data operations on the array to obtain a probability for the set of types including, searching over the array, from the subsequent starting point, for at least one average first reoccurrence distance of the set of types, and, recording the value of the at least one average first reoccurrence distance; and. by the data processor, calculating an average first reoccurrence distance for the set of types of the population, based on adding the value of the at least one average first reoccurrence distance based on items taken from the starting point and the value of the at least one average first reoccurrence taken from the subsequent starting point.

The method is such that the searching is terminated when a predetermined number of reoccurrences of the set of types is found.

The method is such that the predetermined number of reoccurrences is 1.

The method is such that the at least one average first reoccurrence distance of the set of types taken from the starting point includes one of more reoccurrences of the set of types, and, the at least one average first reoccurrence distance of the set of types taken from the subsequent starting point includes one of more reoccurrences of the set of types.

The disclosed subject matter is directed to a method of estimating a probability of at least one event. The method comprises: accessing a database stored on non-transitory computer readable medium, the database including a linear set of strings; selecting a set of strings possessed by the linear set of strings; randomly selecting a first set of strings to serve as a starting point, and inputting the starting point to a data processor, configured for processing Big Data; and, by a data processor programmed to perform Big Data operations on the array to obtain a probability for the set of strings, including, searching over the linear set of strings, from the starting point, for at least one average first reoccurrence distance of the first set of strings, and, recording the value of the at least one average first reoccurrence distance; and, comparing the value for the average first reoccurrence distance between the first set of strings to a threshold value, the threshold value determined based on the first set of strings.

The method is such that it additionally comprises: causing the taking of action for the event, based on the value of the average first reoccurrence with respect to the threshold value.

The method is such that the linear set of strings comprise binary ones and zeros.

The method is such that the binary ones and zeros define bits, and the number of bits of the selected set of strings corresponds to the threshold value.

The method is such that the searching is terminated when a predetermined number of reoccurrences of the set of types is found.

The method is such that the predetermined number of reoccurrences is 1.

The method is such that the at least one average first reoccurrence distance of the set of strings taken from the starting point includes one of more reoccurrences of the set of strings.

As will be understood with reference to the paragraphs and the referenced drawings, provided above, various embodiments of computer-implemented methods are provided herein, some of which can be performed by various embodiments of apparatuses and systems described herein and some of which can be performed according to instructions stored in non-transitory computer-readable storage media described herein. Still, some embodiments of computer-implemented methods provided herein can be performed by other apparatuses or systems and can be performed according to instructions stored in computer-readable storage media other than that described herein, as will become apparent to those having skill in the art with reference to the embodiments described herein. Any reference to systems and computer-readable storage media with respect to the following computer-implemented methods is provided for explanatory purposes, and is not intended to limit any of such systems and any of such non-transitory computer-readable storage media with regard to embodiments of computer-implemented methods described above. Likewise, any reference to the following computer-implemented methods with respect to systems and computer-readable storage media is provided for explanatory purposes, and is not intended to limit any of such computer-implemented methods disclosed herein.

The above-described processes including portions thereof can be performed by software, hardware and combinations thereof. These processes and portions thereof can be performed by computers, computer-type devices, workstations, processors, micro-processors, other electronic searching tools and memory and other non-transitory storage-type devices associated therewith. The processes and portions thereof can also be embodied in programmable non-transitory storage media, for example, compact discs (CDs) or other discs including magnetic, optical, etc., readable by a machine or the like, or other computer usable storage media, including magnetic, optical, or semiconductor storage, or other source of electronic signals.

The processes (methods) and systems, including components thereof, herein have been described with exemplary reference to specific hardware and software. The processes (methods) have been described as exemplary, whereby specific steps and their order can be omitted and/or changed by persons of ordinary skill in the art to reduce these embodiments to practice without undue experimentation. The processes (methods) and systems have been described in a manner sufficient to enable persons of ordinary skill in the art to readily adapt other hardware and software as may be needed to reduce any of the embodiments to practice without undue experimentation and using conventional techniques.