Forensics and CS
DNA profiling is a crucial tool in forensic analysis, aiding in the identification of individuals based on unique genetic markers. By focusing on specific loci in DNA profiles, forensic experts can accurately match samples and provide valuable evidence in court cases. Understanding the significance of DNA uniqueness and the use of high-tech forensics tools like DNA profiling enhances the accuracy of criminal investigations, reducing the likelihood of wrongful accusations. Learn about the science behind DNA analysis and the tradeoffs involved in identifying individuals through their genetic profiles.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Forensics and CS Philip Chan
CSI: Crime Scene Investigation www.cbs.com/shows/csi/ high tech forensics tools DNA profiling Use as evidence in court cases
DNA Deoxyribonucleic Acid Each person is unique in DNA (except for twins) DNA samples can be collected at crime scenes About .1% of human DNA varies from person to person
Forensics Analysis Focus on loci (locations) of the DNA Values at the those loci (DNA profile) are recorded for comparing DNA samples.
Forensics Analysis Focus on loci (locations) of the DNA Values at the those loci (DNA profile) are recorded for comparing DNA samples. Two DNA profiles from the same person have matching values at all loci.
Forensics Analysis Focus on loci (locations) of the DNA Values at the those loci (DNA profile) are recorded for comparing DNA samples. Two DNA profiles from the same person have matching values at all loci. More or fewer loci are more accurate in identification? Tradeoffs?
Forensics Analysis Focus on loci (locations) of the DNA Values at the those loci (DNA profile) are recorded for comparing DNA samples. Two DNA profiles from the same person have matching values at all loci. More or fewer loci are more accurate in identification? Tradeoffs? FBI uses 13 core loci http://www.cstl.nist.gov/biotech/strbase/fbicore.htm
We do not want to wrongly accuse someone How can we find out how likely another person has the same DNA profile?
We do not want to wrongly accuse someone How can we find out how likely another person has the same DNA profile? How many people are in the world?
We do not want to wrongly accuse someone How can we find out how likely another person has the same DNA profile? How many people are in the world? How low the probability needs to be so that a DNA profile is unique in the world?
We do not want to wrongly accuse someone How can we find out how likely another person has the same DNA profile? How many people are in the world? How low the probability needs to be so that a DNA profile is unique in the world? Low probability doesn t mean impossible Just very unlikely
Review of basic probability Joint probability of two independent events P(A,B) = ?
Review of basic probability Joint probability of two independent events P(A,B) = P(A) * P(B) Independent events mean knowing one event does not provide information about the other events P(Die1=1, Die2=1) = P(Die1=1) * P(Die2=1) = 1/6 * 1/6 = 1/36.
Enumerating the events 1 2 3 4 5 6 1 1,1 1,2 2 3 4 5 6 36 events, each is equally likely, so 1/36
Joint probability P(Die1=even, Die2=6) = ?
Joint probability P(Die1=even, Die2=6) = 1/2 * 1/6 = 1/12 P(Die1=1, Die2=5, Die3=4) = ?
Joint probability P(Die1=even, Die2=6) = 1/2 * 1/6 = 1/12 P(Die1=1, Die2=5, Die3=4) = (1/6)3 = 1/216
DNA profile probability How to estimate?
DNA profile probability How to estimate? Assuming loci are independent P(Locus1=value1, Locus2=value2, ...) = P(Locus1=value1) * P(Locus2=value2) * ...
DNA profile probability How to estimate? Assuming loci are independent P(Locus1=value1, Locus2=value2, ...) = P(Locus1=value1) * P(Locus2=value2) * ... How to estimate P(Locus1=value1)?
DNA profile probability How to estimate? Assuming loci are independent P(Locus1=value1, Locus2=value2, ...) = P(Locus1=value1) * P(Locus2=value2) * ... How to estimate P(Locus1=value1)? a random sample of size N from the population and find out how many people out of N have value1 at Locus1
Database of DNA profiles Id A5212 A6921 Locus1 Locus2 Locus3 Locus13
Problem Formulation Given A sample profile (e.g. collected from the crime scene) A database of known profiles Find The probability of the sample profile if it matches a known profile in the database
Breaking Down the Problem Find The probability of the sample profile if it matches a known profile in the database What are the subproblems?
Breaking Down the Problem Find The probability of the sample profile if it matches a known profile in the database What are the subproblems? Subproblem 1 Find whether the sample profile matches 1a: ? 1b: ? Subproblem 2 Calculate the probability of the profile
Breaking Down the Problem Find The probability of the sample profile if it matches a known profile in the database What are the subproblems? Subproblem 1 Find whether the sample profile matches 1a: check entries in the database 1b: check loci in each entry Subproblem 2 Calculate the probability of the profile
Simpler Problem for 1a (very common) Given an array of integers (e.g. student IDs) an integer (e.g. an ID) Find whether the integer is in the array (e.g. whether you can enter your dorm) int[] directory; // student id s int id; // to be found
Linear/Sequential Search Check one by one Stop if you find it Stop if you run out of items to check Not found
Number of Checks (speed of algorithm) Consider N items in the array Best-case scenario When does it occur? How many checks?
Number of Checks (speed of algorithm) Consider N items in the array Best-case scenario When does it occur? How many checks? First item;1 check Worst-case scenario When does it occur? How many checks?
Number of Checks (speed of algorithm) Consider N items in the array Best-case scenario When does it occur? How many checks? First item;1 check Worst-case scenario When does it occur? How many checks? Last item or not there; N checks Average-case scenario Average of all cases (1 + 2 + + N) / N = [N(N+1)/2] / N = (N+1)/2
Matching DNA profiles Each profile has 13 loci Do we always need to check all 13 loci to decide if a match occurs or not?
Can we do better? Faster algorithm? What if the array is sorted, items are in an order E.g. a phone book
Binary Search 1. Check the item at midpoint 2. If found, done 3. Otherwise, eliminate half and repeat 1 and 2
Breaking down the problem While more items and not found in the mid point What are the two subproblems?
Breaking down the problem While more items and not found in the mid point Eliminate half of the items Determine the mid point
Number of checks (Speed of algorithm) Best-case scenario When does it occur? How many checks?
Number of checks (Speed of algorithm) Best-case scenario When does it occur? How many checks? In the middle; 1 check
Number of checks (Speed of algorithm) Best-case scenario When does it occur? How many checks? In the middle; 1 check Worst-case scenario When does it occur? How many checks?
Number of checks (Speed of algorithm) Best-case scenario When does it occur? How many checks? In the middle; 1 check Worst-case scenario When does it occur? How many checks? Dividing into two halves, half has only one item ? checks
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1 = [ T(N/4) + 1 ] + 1
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1 = [ T(N/4) + 1 ] + 1
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1 = [ T(N/4) + 1 ] + 1 = [ [ T(N/8) + 1] + 1] + 1
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1 = [ T(N/4) + 1 ] + 1 = [ [ T(N/8) + 1] + 1] + 1 = any pattern?
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1 = [ T(N/4) + 1 ] + 1 = [ [ T(N/8) + 1] + 1] + 1 = = T(N/2k) + k
Number of checks (Speed of algorithm) T(1) = 1 T(N) = T(N/2) + 1 = [ T(N/4) + 1 ] + 1 = [ [ T(N/8) + 1] + 1] + 1 = = T(N/2k) + k N/2k gets smaller and eventually becomes 1
