Rafe Rafe

Bioinformatics

• Final Round. Problem 1 Gene Expression

  Bioinformatics/Bioinformatics Contest 2017 2019. 8. 28. 23:37

  https://stepik.org/lesson/32224/step/2?unit=19659 Problem 1 Problem 1 stepik.org 하나의 genome에서 유래한 expression level을 구하는 문제이다. N개의 genome과 그것들로부터 유래된 rna 조각들을 M개를 주었을때 하나의 genome으로 부터 유래한 rna의 갯수를 세어야 한다. 즉 2개의 genome과 겹치는 rna들을 제외해야 한다. 간단하게 생각해보면 다음과 같은 코드로 가능하다. import sys from functools import reduce import bisect input = [] # with open('F1') as f: # for line in f.readlines(): # input.append(..

  Read More
• Burrows-Wheeler Transform (버로우스-휠러 변환)

  Bioinformatics 2019. 8. 2. 23:58

  BWT는 bzip2에서 사용되는 알고리즘 중 하나이다. 비슷한 단어(패턴)이 많다는 점에 착안하여 그것들을 모음으로써 run length encoding을 사용할 수 있게끔 해준다. 예를들어 'very_very_very_very_long'이라는 문장에 BWT를 적용한다면 'gyyyyvvvvn_oleeee___$rrrr'가 되며 run length encoding을 적용하게 되면 'g4y4vn_ol4e3_$4r'이 된다. 변환 과정은 https://ko.wikipedia.org/wiki/%EB%B2%84%EB%A1%9C%EC%9A%B0%EC%A6%88-%ED%9C%A0%EB%9F%AC_%EB%B3%80%ED%99%98 버로우즈-휠러 변환 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전...

  Read More
• Pigeonhole Principle for Approximate Sequence Matching

  Bioinformatics 2019. 6. 23. 19:06

  비둘기집원리는 예전부터 지겹도록 듣던 원리중 하나이다. 매우 직관적이고 쓰이는곳도 많지만 approximate sequence matching을 위해서 사용될 수도 있다. Approximate matching은 exact matching과 반대된다고도 할 수 있다. Exact matching은 정확하게 sequence가 같아야 하지만 approximate matching은 어느정도의 edit distance를 허용한다. Edit distance는 수정거리를 뜻한다. 두개의 seq가 있을때 한 seq를 다른 seq로 변형할때 최소한의 편집으로 횟수를 뜻한다. 수정이란 삽입, 삭제, 변형을 뜻한다. 예를들어 AAGTTAC AACTTAGC 두개의 seq가 주어졌을때 edit distance는 2이다. AAGT..

  Read More
• Error Correction in Reads

  Bioinformatics/Rosalind 2019. 6. 19. 14:45

  http://rosalind.info/problems/corr/ ROSALIND | Error Correction in Reads It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Error Correction in Reads solved by 1467 2012년 7월 2일 12:00:00 오전 by Mikhail Dvorkin Topics: Genome Assembly Genome Sequencing Isn't Perfect In “G rosalind.info DNA seq에서 하나의 base에 err가 발생했을때 이를 교정하는 문제이다. 입력된 seque..

  Read More
• Finding a Spliced Motif

  Bioinformatics/Rosalind 2019. 6. 19. 14:40

  http://rosalind.info/problems/sseq/ ROSALIND | Finding a Spliced Motif It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Finding a Spliced Motif solved by 3298 2012년 7월 13일 12:00:00 오전 by Rosalind Team Topics: String Algorithms Motifs Are Rarely Contiguous In “Findi rosalind.info Bioinformatics Contest 2017의 Qualification Round 3와 사실상 ..

  Read More
• k-Mer Composition

  Bioinformatics/Rosalind 2019. 6. 18. 23:26

  http://rosalind.info/problems/kmer/ ROSALIND | k-Mer Composition It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. k-Mer Composition solved by 2226 2012년 7월 13일 12:00:00 오전 by Gabriel Valiente Topics: String Algorithms Generalizing GC-Content Figure 1. The 2-m rosalind.info input으로 들어온 fasta파일에 있는 sequence에 k-mer의 각각의 갯수를 세서 사전순서대로 출력해..

  Read More
• Completing a Tree

  Bioinformatics/Rosalind 2019. 6. 17. 23:37

  http://rosalind.info/problems/tree/ ROSALIND | Completing a Tree It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Completing a Tree solved by 2689 2012년 7월 11일 12:00:00 오전 by Rosalind Team Topics: Graph Algorithms, Phylogeny The Tree of Life Figure 1. A phylo rosalind.info adjacency list를 입력으로 주고 그 리스트들을 하나의 tree로 만들려면 몇개의 최소 edge가 필요..

  Read More
• Genome Assembly as Shortest Superstring

  Bioinformatics/Rosalind 2019. 6. 13. 22:39

  http://rosalind.info/problems/long/ Bioinformatics contest 2019의 Final Round의 4번문제인 Minimal Genom이 생각나는 문제였다. Dynamic을 쓸 수 있을것 같아 보이지만 그렇지 않다. 선택이나 그런게 아닌 모든 경우의 수를 생각해야하는 np complete 문제이기 때문이다. from util.read import read_fasta def weld_seq(seq1, seq2): for weld_len in reversed(range(min(len(seq1), len(seq2)))): if seq1[-weld_len:] == seq2[0: weld_len]: return seq1 + seq2[weld_len:] return seq1 ..

  Read More