Molecular biology and genetics provide "natural" examples of modelable objects such as linear sequences of symbols in a finite alphabet.
Thus each chromosome, carrying the genetic capital, is essentially composed of two strands of DNA: each of these strands can be modeled (disregarding the three-dimensional helical structure) as a succession of nucleotides, each composed of a phosphate or phosphoric acid, a sugar (deoxyribose) and a nitrogen base. There are four different bases: two are called purine (guanine G and adenine A), the other two are pyrimidine (cytosine C and thymine T), which work "in pairs", thymine always binding to the body. adenine and cytosine always to guanine. Since the information encoded in these databases determines a large part of the genetic information, a useful model of a chromosome strand consists of the simple linear sequence of the bases that compose it, in fact a (very long) sequence defined on a four-letter alphabet (ATCG).
From this model, the question arises of knowing how to search for particular sequences of nucleotides in a chromosome or to detect similarities / dissimilarities between two (or more) DNA fragments. These genetic similarities will serve, for example, to quantify evolutionary proximities between populations, to locate genes fulfilling the same functions in two neighboring species or to carry out tests of familiarity between individuals. Searching for sequences and measuring similarities are therefore two basic problems of bioinformatics.
This type of calculation is not limited to genes and is also used for proteins. Indeed, the primary structure of a protein can be modeled by the simple linear sequence of the amino acids it contains and which determines some of the properties of the protein. Since the amino acids are also in finite number (20), the proteins can then be modeled as finite sequences on an alphabet with 20 letters.
The problem is to prevent a factorial explosion in the number of comparisons. May I suggest:
1. Each sequence of bases is represented by an array.
2. From each base, i.e. each array element, we identify the following sequence of n bases. e.g. if n == 3, we have sequences of 4 bases and there are 4**4 = 256 possible sequences. The identifiers for the sequences are stored in a parallel array, starting from each base in turn.
3. We search the arrays to be compared for the same sequence number. Where this occurs, the first 4 bases match.
4. We traverse the two arrays of bases (Not the sequence array) counting the number of matches, the number of mis-matches and the number of missing or inserted bases. When the number of errors reaches a criterion we reject the sequence. When it reaches a criterion total length we accept it.
e.g. base sequence
g a c t t a t a a g a t a g g c t
aaaa = 0 aaac = 1 aaag = 2 aaat = 3
aaca = 5 aacc = 6 aacg = 7 aact = 8 etc.
The sequence codes are
g a c t t a t a a g a t a g g c t
135 31 124 243 204 48 194 8 35 140 50 202 41 167
We search the other sequence arrays for the base sequences to be compared for 135. The first 4 bases match. We continue the comparison from there. Computing the sequence codes is a single pass through the data and will be computationally cheap.
Best wishes,
John
- Badges
- Science topic
- Similar topics
- Biological Science
- Histology
- Sectioning