Ծրագրավորում 01

🟠 ԴՆԹ նույնականացում

🤖
Այս խնդրում, մենք կփորձենք նույնականացնել մարդուն՝ օգտագործելով նրա ԴՆԹ ինֆորմացիան։
ԴՆԹ ինֆորմացիան թույլ է տալիս միարժեքորեն նույնականացնել յուրաքանչյուր անհատի։ Այս մեթոդը լայնորեն օգտագործվում է գրեթե բոլոր երկրների արթարադատության համակարգերում։
Նախորդ խնդրում մենք դիտարկեցինք բիոինֆորմատիկայի հիմնական գաղափարները։ ԴՆԹ ներկայացվում է A T G C նուկլեոտիդների հաջորդականությամբ և 99.6% մարդկանց մոտ այդ շղթաները նույնական են։ Բացի SNP կետերից, մարդկանց ԴՆԹ շղթաներում տարբերությունները շատ հաճախ նաև հանդիպում են նաև այսպես կոչված STR (short tandem repeats) հաջորդականություններում։ STR-ները դրանք ԴՆԹ նուկլեոտիդների կարճ հաջորդականություններ են, որոնք հաջորդաբար կրկնվում են ԴՆԹ շղթայի այս կամ այն հատվածներում։
“CTAG” STR հաջորդականությունը տարբեր մարդկանց ԴՆԹ շղթաներում։
“CTAG” STR հաջորդականությունը տարբեր մարդկանց ԴՆԹ շղթաներում։
 
🧬
STR-ների կրկնության քանակը տարբեր մարդանց մոտ շատ հաճախ տարբերվում է։ Օգտագործելով STR-ների կրկնությունների քանակի տարբերությունը, հնարավոր է միարժեքորեն նույնականացնել յուրքանչյուր մարդու։
“AGAT” STR-ի կրկնության քանակը տարբերությունը Արփիի և Արամի ԴՆԹ շղթաներում։
“AGAT” STR-ի կրկնության քանակը տարբերությունը Արփիի և Արամի ԴՆԹ շղթաներում։
 
ℹ️
Հավանականությունը, որ երկու տարբեր մարդկանց մոտ մեկ STR-ի կրկնության քանակը կհամնկնի, մոտովորապես 5% է։ Եթե նույնականացման պրոցեսում օգտագործվեն 10 տարբեր STR -ներ, ապա հավանականությունը, որ երկու տարբեր մարդկանց մոտ բոլոր 10 STR-ների կրկնությունների քանակը կհամնկնի հավասար է ❗(քվադրիլոն) ։
ԱՄՆ հետաքննությունների դաշնային բյուրոի CODIS ԴՆԹ տվյալների բազան նույնականացման համար օգտագործում են միչև 20 տարբեր STR-ներ, ինչը սխալմունքի հավանականությունը մոտեցնում է զրոյի։
Խնդրի պարզության համար կարող ենք համարել, որ ԴՆԹ տվյալների բազան գտնվում է ֆայլում, իսկ նույնականացումը կատարվում է ընդհամենը 3 STR ների համընկմամբ։ Մուտքային Ֆայլը ունի հետևյալ ֆորմատը՝
  • Ֆայլի յուրաքանչյուր տող պարունակում է անհատ մարդու STR-ների մասին ինֆորմացիա։
  • Առաջին տողում գրված է name, surname բառերը, որոնց հաջորդում են 3 STR հաջորդականությունների անուններ (օրինակ AGAT, AATG, TATC, GATA և այլն) 
name,surname,AGAT,AATG,TATC
Alice,Cooper,28,42,14
Bob,Wasovski,17,22,19
Charlie,Chaplin,36,18,25
STR կրկնությունների տվյալների բազայի օրինակ։
Բերված օրինակում, Alice Cooper անունով մարդու ԴՆԹ-ում AGAT STR-ը կրկնվում է 28 անգամ, AATG STR-ը 42, իսկ TATC STR -ը 14 անգամ։ Bob Wasovski անունով մարդու մոտ նույն երեք STR-ները հանդիպում են համապատասխանաբար 17, 22 և 19 անգամ։ Charlie Chaplin անունով մարդու մոտ նույն STR-ները հանդիպում են համապատասխանաբար 36, 18, 25 անգամ։
Դե ինչ, եկե՛ք գրենք ծրագիր, որը կօգնի նույնականացնել անհատին։ Ծրագիրը, որպես մուտք ստանում է՝
  1. Տվյալների բազայի ֆայլը՝ dnaBase.txt անունով։
  1. Տեքստային , որտեղ պահվում է փնտրվող մարդու ԴՆԹ շղթան` dnaToMatch.txt անունով։
      2. AGACGGGTTACCATGACTATCTATCTATCTATCTATCTATCTATCTATCACGTACGTACGTATCGAGATAGATA
Փնտրվող ԴՆԹ շղթայում, յուրաքանչյուր STR -ի համար (տվյալների բազայի առաջին տող) ծրագիրը պետք է հաշվի դրա ամենաերկար հաջորդական կրկնության քանակը։
  1. Եթե բոլոր երեք STR-ների ամենաերկար հաջորդական կրկնության քանակը համընկնում է տվյալների բազայի որևէ տողի հետ, ծրագիրը էկրանին պետք է տպի համապատասխան մարդու անունը և ազգանունը։
  1. Եթե կրկնություների քանակը չի համընկնում ոչ մի տողի հետ, ծրագիրը պետք է էկրանին տպի “No Match” տողը։
 
Օրինակ, եթե ունենք հետևյալ բազայի ֆայլը՝
name,surname,AGAT,AATG,TATC
Armen,Karapetyan,5,2,8
Karen,Poghosyan,3,7,4
Gohar,Davtyan,6,1,5
dnaBase
ապա, AACCCTGCGCGCGCGCGATCTATCTATCTATCTATCCAGCATTAGCTAGCATCAAGATAGATAGATGAATTTCGAAATGAATGAATGAATGAATGAATGAATG ԴՆԹ համատասխանում է Կարեն Պողոսյանին, քանի որ՝
  • AGAT STR-ը հաջորդական կրկնվում է 3 անգամ։
notion image
  • AATG STR-ը հաջորդական կրկնվում է 7 անգամ։
notion image
  • TATC STR-ը հաջորդական կրկնվում է 4 անգամ։
notion image
 

Հուշում 1

Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue