GeezerVison is showing github.com — ClassicComputerScienceProblemsInPython/Chapter2/dna_search.py at master · sqrf/ClassicComputerScienceProblemsInPython

Expand file tree

dna_search.py

Copy path

More file actions

Latest commit

History

69 lines (55 loc) · 2.22 KB

dna_search.py

Copy path

File metadata and controls

69 lines (55 loc) · 2.22 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

# dna_search.py

# From Classic Computer Science Problems in Python Chapter 2

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

# http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

from enum import IntEnum

from typing import Tuple, List

Nucleotide: IntEnum = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))

Codon = Tuple[Nucleotide, Nucleotide, Nucleotide] # type alias for codons

Gene = List[Codon] # type alias for genes

gene_str: str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

def string_to_gene(s: str) -> Gene:

gene: Gene = []

for i in range(0, len(s), 3):

if (i + 2) >= len(s): # don't run off end!

return gene

# initialize codon out of three nucleotides

codon: Codon = (Nucleotide[s[i]], Nucleotide[s[i + 1]], Nucleotide[s[i + 2]])

gene.append(codon) # add codon to gene

return gene

my_gene: Gene = string_to_gene(gene_str)

def linear_contains(gene: Gene, key_codon: Codon) -> bool:

for codon in gene:

if codon == key_codon:

return True

return False

acg: Codon = (Nucleotide.A, Nucleotide.C, Nucleotide.G)

gat: Codon = (Nucleotide.G, Nucleotide.A, Nucleotide.T)

print(linear_contains(my_gene, acg)) # True

print(linear_contains(my_gene, gat)) # False

def binary_contains(gene: Gene, key_codon: Codon) -> bool:

low: int = 0

high: int = len(gene) - 1

while low <= high: # while there is still a search space

mid: int = (low + high) // 2

if gene[mid] < key_codon:

low = mid + 1

elif gene[mid] > key_codon:

high = mid - 1

else:

return True

return False

my_sorted_gene: Gene = sorted(my_gene)

print(binary_contains(my_sorted_gene, acg)) # True

print(binary_contains(my_sorted_gene, gat)) # False