My Blog

Latest blog

Intro

 Microbiome은 microbiota와 genome의 합성어로 각각의 의미는 다음과 같습니다.
    * microbiota: ecological communities of commensal, symbiotic and pathogenic microorganisms
    * genome: genetic material of an organism

 즉, 인간, 동식물, 대기, 바다, 토양 등 주변 환경에 서식하는 microbe와 그들의 유전체 정보를 의미합니다. 최근에 신체 내, 외부에 공생하는 microbe가 비만, 아토피, 암 등 각종 질환과 밀접한 연관을 가지고 있다는 연구결과가 발표되고 있습니다. 건강한 삶에 대한 관심이 증가하면서 environmental microbiome 분야의 연구도 활발하게 이루어지고 있습니다.
 본 포스트에서는 NGS 데이터를 활용한 microbiome analysis에 대해 관련 논문을 중심으로 살펴보겠습니다.

Understand of Microbiome Analysis

 Microbiome 연구는 HTS(high-hroughput sequencing) 기술 발전과 함께 급격히 성장했고 다량의 데이터가 생산되고 있습니다. 분석 대상에 따라, HTS method에 따라 이들이 가지는 장점과 한계에 대해서 알아보겠습니다.


 1. 분석 대상
    1) Microbes: culturome
    2) DNA: Amplicon(16S/18S/ITS), Metagenome, Virome
    3) mRNA: Virome, Metatranscriptome

 2. HTS method
    1) Culturome: microbe-level에서 microbe를 배양하고 확인하는 방법입니다. bacterial stocks를 얻기 위한 가장 효율적인 방법이지만, 비용이 많이 들고 노동 집약적인 특징을 가집니다.
    2) Amplicon (16S/18S/ITS): prokaryotes는 16S ribosome DNA (rDNA), eukaryotes는 18S rDNA와 internal transcribed spacers(ITS)를 포함한 영역을 주요 마커로 사용하여 amplicon sequencing을 진행하는 방법입니다. 주로 Illumina sequencer를 사용하며 paired-end 250bp 길이로 데이터를 생산합니다. 적은 양의 시료를 가진 샘플이나 host DNA에 contam된 샘플에 적용 가능하지만, 단지 genus-level까지만 확인할 수 있고 특정 primer와 PCR cycle 수에 민감한 특징을 가집니다.
    3) Metagenome: amplicon 방식에 비해 더 많은 정보를 제공합니다. taxonomic 정보 뿐만이 아니라 functional 정보까지 얻을 수 있습니다. 하지만 상대적으로 비용이 많이 들고 분석시간이 오래 걸리는 특징을 가집니다.
    4) Virome: DNA나 RNA를 가지는 virus 특성상 두 개 시료 모두 사용 가능하며 metagenome과 metatranscriptome 분석을 조합하여 사용합니다. 시료 양이 적으므로 virus enrichment나 host DNA 제거가 필수입니다. 하지만 가장 비용이 많이 들고 분석하기 어려운 특징을 가집니다.
    5) Metatranscriptome: microbial community의 mRNA를 profiling 하고 gene expression level을 확인하며 functional 정보를 확인할 수 있습니다. 비용이 많이 들고 분석 방법이 복잡한 특징을 가집니다.

 샘플 type과 정답을 알고자 원하는 질문 내용에 따라 HTS method를 선택합니다. 여러 가지 방식을 통합하여 분석하는 것이 권장되는데, 이러한 multi-omics 방식은 microbiome의 taxonomy와 function에 대한 insight를 제공하기 때문입니다.

Analysis Pipeline

 Microbiome 분석을 위한 다양한 tool와 pipeline이 공개되어 있습니다. Amplicon/metagenomic 분석을 위한 current best-practice pipeline을 알아보겠습니다.


 1. Amplicon analysis
    1) QIIME/USEARCH 사용: raw reads를 feature table로 변환하는 과정
    2) Step1 - demultiplexing: raw amplicon paired-end reads를 barcode sequence에 따라 grouping하는 단계
    3) Step2 - merging: paired-end reads를 하나의 amplicon sequence로 합치고 barcode와 primer sequence를 제거하는 단계
    4) Step3 - quality control: low-quality amplicon sequence를 제거하는 단계
    5) Step4 - picking the representative sequences: amplicon 분석의 가장 중요한 단계로 두 가지 방식을 주로 사용
        A) OTUs (operational taxonomic units): 97% 이상 동일한 sequence를 하나의 OTU로 clustering하는 방식 (UPARSE 알고리즘). 하지만 species나 strain 사이 미묘한 차이는 검출하지 못할 수 있음
        B) ASVs (amplicon sequence variants): 동일한 sequence를 하나의 ASV로 clustering하는 방식 (denoising 알고리즘). OTU와 비슷하지만 1 base 차이만 나도 서로 다른 그룹으로 분리할 수 있으므로 더 정확하고 세밀한 분류가 가능. 최근 OTU보다 ASV를 더 많이 사용하는 추세이며 분석에 DADA2/Deblur tool 사용
    6) Step5 - obtaining feature table (OTU/ASV table): 각 샘플마다 feature sequence의 빈도를 측정. 동시에 feature sequence에 kingdom, phylum, class, order, family, genus, and species level의 taxonomy를 할당
    7) (additional) Step6 - functional prediction: 보통 amplicon sequencing은 taxonomic 정보만 얻는 목적으로 수행하지만 근래에 potential functional information을 예측하는 tool이 개발
        A) PICRUSt: Greengenes DB의 OTU table 기반으로 KEGG (Kyoto Encyclopedia of Genes and Genomes) pathway의 metagenomic functional composition 예측
        B) PICRUSt2: OTU/ASV table 기반으로 metagenomic functions 직접 예측
        C) Tax4Fun: SILVA DB 기반으로 KEGG functional capabilities 예측
        D) FAPROTAX pipeline: functional annotation of prokaryotic taxa. published metabolic & ecological functions 기반으로 functional annotation 수행하는 파이프라인
        E) BugBase: Greengenes의 확장판 DB. oxygen tolerance, gram staining, pathogenic potential 같은 phenotype 예측할 때 사용. 주로 medical research 분야에서 사용



 2. Metagenomic analysis
 Amplicon 분석과 비교할 때 much higher resolution of taxonomic annotation 정보와 functional 정보까지 제공한다는 장점이 있습니다. 하지만 대량의 데이터를 다루어야 하므로 linux system에서 다량의 computing resources가 필요합니다.
    1) Step1 - quality control & removal of host contamination: KneadData pipeline/Trimmomatic + Bowtie2 사용
    2) Step2 - convert clean data into taxomomic and functional tables: reads-based method or/and assembly-based method 사용
        A) reads-based method
            a) clean reads를 DB에 align하고 feature table 생성
            b) MetaPhlAn2, Kraken2 (lowest common ancestor 알고리즘), HUMAnN2, MEGAN 등 사용
        B) assembly-based method
            a) clean reads를 assemble하여 contig 만들고 gene abundance table 생성
            b) MEGAHIT (quick & little memonry) or metaSPAdes (longer contigs & more computational resources) 사용
            c) assembled contig 내 gene 확인: metaGeneMark or Prokka
            d) redundant gene 제거: CD-HIT
            e) gene abundance table 생성: Bowtie2 or Salmon
            f) 일반적으로 존재하는 다량의 gene은 functional annotation에 따라 묶어서 KEGG Orthology (KO) module과 pathway와 같이 축소된 차원 형태로 나타냄
    3) (additional) Step3 - to mine gene clusters or to assemble draft microbe genomes
        A) to mine gene cluster
            a) secondary metabolite biosynthesis와 연관된 gene cluster를 확인, annotation, visualization 하는데 antiSMASH DB 사용
        B) to assemble draft microbe genomes
            a) 기존에 알려진 microbe의 reference genome 숫자에 비해 자연에 존재하는 microbe의 숫자와 다양성은 훨씬 큼
            b) 따라서 align하여 taxonomic & functional 정보 분석은 매우 제한됨
            c) 이러한 한계를 극복하기 위해서 상호 연관성 있는 gene의 구간화 (binning)를 이용한 metagenome assembled genome (MAG) analysis를 사용하여 draft microbe genome을 구축함
            d) binning tools: CONCOCT or MaxBin2 or MetaBAT2
            e) binning pipelines: MetaWRAP or DAStool

Statistical Analysis and Visualization

 Amplicon과 metagenomic analysis의 가장 중요한 결과물은 taxonomic & functional table입니다. 앞서 우리는 'Understand of Microbiome Analysis' 파트에서 정답을 알고자 원하는 질문 내용에 따라 적절한 HTS method를 선택해야 한다고 알아봤습니다. 마찬가지로 최종 결과물을 생성할 때에도 어떤 질문에 답변할 것인지에 따라 overall or details statistical analysis and visualization을 선택합니다.
 Overall analysis는 feature table에서 alpha/beta- diversity와 taxonomic composition의 차이를 알아볼 때 사용합니다. Detail analysis는 comparison, correlation analysis, network analysis, machine learning 등을 사용한 biomarker 확인에 사용합니다.


 1. Alpha diversity
 Richness와 evenness 척도를 포함하여 하나의 샘플 내에서 diversity를 평가합니다.
    1) QIIME or USEARCH 사용
    2) 그룹 간의 alpha diversity 차이 측정: Analysis of Variance (ANOVA), Mann-Whitney U Test, KruskalWallis test 사용하여 통계적 평가
    3) 이 때 각 그룹 비교시 두 번 이상 측정하는 경우 adjusted P-value 사용해야 함을 주의

 2. Beta diversity
 샘플 간 microbiome 구성 차이를 확인합니다.
    1) 보통 차원 축소 방식의 조합으로 확인
    2) principal coordinate analysis (PCoA), non-metric multidimensional scaling (NMDS), constrained principal coordinate analysis (CPCoA) 사용
    3) beta diversity 간 통계적 차이 확인: permutational multivatiate analysis of variance (PERMANOVA) 사용

 3. Taxonomic composition
    1) microbial community에 존재하는 mocrobiota에 대한 설명
    2) 결과는 a stacked bar plot으로 표현

 4. Difference comparison
그룹 간 현저하게 차이를 보이는 features (such as species, genes, or pathways)를 확인합니다.
    1) Welch's t-test, Mann-Whitney U test, Kriskal-Wallis test, ALDEx2, edgeR, STAMP, LEfSe 사용
    2) 결과는 a volcano plot, Manhattan plot, extended error bar plot으로 표현

 5. Correlation analysis
 샘플의 metadata와 taxa 사이 상관관계를 보여줍니다. 예를 들어 taxa와 pH, longitude, latitude, clinical indices와 같은 환경요소 사이의 상관관게를 확인합니다. 또한 특정 시점에 microbiota에 영향을 주는 key environmental factors를 확인합니다.
 
 6. Network analysis
 전체적인 관점에서 features의 동시 발생을 탐색합니다. Correlation network의 속성은 co-occurring taxa 혹은 functional pathways 간의 잠재적 상호작용을 의미할 수 있습니다.
    1) analysis: SparCC package 사용
    2) visualization: R library igraph, Cytoscape, Gephi 사용

 7. Machine learning
    1) 데이터로부터 학습, pattern 확인, 결정 과정을 거치는 AI의 한 분야
    2) microbiome 분야에서는 taxonomic classification, beta-diversity analysis, binning, compositional analysis of particular features 확인에 주로 사용

 8. Treemap
    1) phylogenetic tree 만들 때 사용
    2) IQ-TREE (for big data), iTOL (online visualization. input 파일은 table2itol 사용), GraPhlAn (recommend) 사용

 9. (additional) Analysis
    1) microbial origin 확인: FEAST, SourceTracker 사용
    2) host와 microorganism으로부터 genetic information을 통해 regulatory relationship 확인: genome-wide association analysis (GWAS) 사용


Summary

 주변 환경에 서식하는 microbe 대부분은 아직 genomic information이 밝혀지지 않은 미지의 세계에 놓여 있습니다. Microbe가 사람의 삶에 미치는 영향이 지대하다는 사실이 밝혀지면서 관련 연구도 증가하는 추세입니다.
 NGS를 활용한 microbiome analysis는 specimen과 HTS methods에 따라 장점과 한계가 명확합니다. 따라서 어떤 질문에 대한 답을 얻기 원하는지 명확하게 정리한 다음 목적에 맞는 방법을 선택하는 것이 효율적입니다.
 분석은 amplicon 방식과 metagenomic 방식 두 가지로 분류할 수 있습니다.
 Amplicon 방식은 16S/18S/ITS 영역 대상으로 250PE amplicon data를 생산합니다. OTU/ATVs로 알려진 representative sequence를 추려내고 taxonomic 정보를 annotation 하는 것이 분석의 핵심 과정입니다.
 Metagenomic 방식은 대상에서 채취한 DNA 시료로부터 shotgun NGS data를 생산합니다. 마찬가지로 cleaned reads로부터 taxonomic & functional table을 만드는 과정이 핵심 단계입니다.
 위에서 얻은 feature table은 이후 통계분석과 visualization tool을 활용하여 질문에 대한 알맞은 결과를 생산합니다.




  본 글은 DFS에 이어 작성된 글입니다. 먼저 DFS를 읽고 오시는 것을 권장합니다.


Algorithm: BFS

 DFS의 단점 중 하나는 항상 최적의 솔루션을 찾는 것이 아니라는 것입니다. BFS는 이런 단점을 보완한 검색 방법입니다. 전반적으로 DFS와 유사하므로 동일한 부분은 생략하고 차이나는 부분 위주로 살펴보겠습니다.

Algorithm: BFS Process

 검색 문제는 아래와 같은 과정에 따라 접근합니다.
 1. Frontier는 초기 상태(A)를 포함한 상태, Explored set은 비어있는 상태에서 시작합니다.
 2. 아래 과정들을 반복합니다.
   1) Frontier에 검색할 다음 노드 node가 존재하는지 확인합니다. 만약 비어 있다면 솔루션은 없으며 검색 과정을 종료합니다. 참고로 노드란 상태 state, 부모 노드 parent node, 행동 action, 비용 path cost에 대한 정보를 담고 있는 데이터 구조라고 볼 수 있습니다.
    2) 노드 가져오기: Frontier에서 첫 번째 노드를 추출합니다. (queue 구조)
    3) 솔루션 확인과 리턴: 만약 2)의 노드가 목표하는 노드라면 검색과정을 종료하고 솔루션을 리턴합니다.
    4) 노드 추가: Explored set에 노드를 추가합니다.
    5) Frontier 확장: Frontier에 하위 노드(child node)를 추가합니다. 이 때 하위 노드가 frontier와 explored set에 존재하는지 확인합니다. 만약 존재한다면 하위 노드는 추가할 수 없습니다.




 위 과정에서 DFS와 어떤 차이점을 찾아볼 수 있을까요?
 검색 과정에서 DFS는 마지막 노드(F)를 만날 때까지 계속 하위 노드를 찾아갑니다. 하지만 BFS는 우선 같은 깊이의 모든 노드(C, D)를 우선 검색합니다. 매번 검색하는 노드가 목표 노드(E)와 일치하는지 비교한 뒤 일치한다면 검색 과정을 종료합니다.
 이처럼 동일한 깊이의 모든 노드로 확장하며 검색하는 방식이 BFS Breadth First Search입니다. BFS는 queue 구조를 사용하여 노드를 검색합니다.

 노드의 수를 V Vertex, 연결선의 수를 E Edge라고 할 때, BFS의 공간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다. 시간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다.

 BFS의 장, 단점은 아래와 같습니다.
  • ⊙ 장점
  • ▷ 여러개의 솔루션이 존재할 때 최단경로를 찾을 수 있습니다.
  • ⊙ 단점
  • ▷ 검색 해야할 노드가 많은 경우 필요없는 노드까지 모두 저장해야 하므로 DFS보다 큰 저장공간이 필요합니다.
  • ▷ 노드의 수가 많을수록 검색 시간이 오래 걸립니다.

Algorithm: BFS Code

 BFS를 미로찾기 문제에 적용해 보겠습니다.



 'QueueFrontier' 클래스는 'StackFrontier' 클래스를 상속 받습니다.
 다만 DFS와 차이점은 'remove' 함수가 frontier에서 노드를 가져올 때 가장 첫 번째 위치에 존재하는 노드를 가져온다는 것입니다. Queue 자료 구조를 사용합니다. 그 외 코드는 DFS와 동일합니다.
 전체 코드와 예제 파일은 이 곳에서 확인할 수 있습니다.

Algorithm: BFS Example

 앞서 실제 미로 문제 파일을 DFS로 풀 때, 가까운 솔루션을 두고 멀리 돌아가는 솔루션을 리턴한 케이스가 있었습니다. 이번에는 BFS를 적용해서 풀어보겠습니다.




 BFS의 장점으로 알아봤던 것처럼 최적의 솔루션을 찾아냈습니다.

Problems

 다음과 같은 퍼즐 문제를 한 번 즈음 풀어보셨을 겁니다.
 하나의 빈 칸이 존재하고 주위의 숫자칸을 빈 칸으로 옮겨서 최종 숫자 순서대로 정렬하는 퍼즐입니다.




 다음은 미로 문제입니다.
 입구에서 출발하여 출구로 나가는 길을 찾아야 합니다. 막다른 길을 만나면 되돌아가서 다른 길을 찾아야 합니다.




 마지막으로 최적경로 찾기 문제입니다.
 매일 출퇴근하는 경로입니다. 버스를 환승하고 1호선 혹은 7호선을 이용합니다. Door to door는 1시간 40분 소요되는데... 직주근접은 정말 소중합니다...
이처럼 우리는 종종 목적지까지 가장 빠른 길을 찾아야 할 때가 있습니다.



 과연 이 문제들을 어떻게 논리적으로 해결할 수 있을까요?

Algorithm: DFS

 검색 알고리즘은 위와 같은 문제들에 대한 답을 구할 수 있습니다.

 검색 알고리즘은 연속 변수나 이산 변수를 사용하여 일부 데이터 구조 안에 저장된 정보를 검색하거나 검색 공간에서 계산을 하기 위해 사용합니다.

 에이전트 agent는 주변 환경 environment을 인식하고 상호작용하는 주체입니다. 환경 내에서 에이전트가 배치된 모양을 상태state라고 일컫습니다. 에이전트에게 어떤 환경 안에서 문제가 주어졌을 때 현명한 결정을 내리려면 어떤 행동 actions이 가장 좋은지 검색하고 실행에 옮겨야 합니다. 현실에서 곧바로 실행할 수 없기 때문에 모델을 사용하여 simulation을 합니다.
 이처럼 검색 과정을 통해 다양한 솔루션 solution을 얻을 수 있으며 가장 비용이 적게 드는 솔루션을 optimal solution이라고 합니다.

 검색 문제는 다음과 같이 구성됩니다.

  • ⊙ 초기 상태 initial state: 에이전트가 환경 안에서 행동을 시작하기 전 초기 위치입니다.
  • ⊙ 행동 actions: 현재 상태에서 선택 가능한 행동들을 의미합니다. ACTIONS(s)는 상태 s에서 실행가능한 모든 행동들을 반환합니다.
  • ⊙ 전이모델 transition model: 특정 상태에서 가능한 행동을 수행한 결과 나타나는 상태들을 설명하는 모델입니다. RESULT(s, a)는 상태 s에서 행동 a를 수행한 결과 상태를 반환합니다.
  • ⊙ 평가 goal test: 행동의 결과로 얻어진 상태가 처음 목표로 했던 상태인지 평가하는 것입니다.
  • ⊙ 비용 함수 path cost function: 주어진 경로를 거쳐감에 따라 소요되는 비용을 산출하는 함수입니다.

Algorithm: DFS Process


 검색 문제는 아래와 같은 과정에 따라 접근합니다.
 1. Frontier는 초기 상태(A)를 포함한 상태, Explored set은 비어있는 상태에서 시작합니다.
 2. 아래 과정들을 반복합니다.
   1) Frontier에 검색할 다음 노드 node가 존재하는지 확인합니다. 만약 비어 있다면 솔루션은 없으며 검색 과정을 종료합니다. 참고로 노드란 상태 state, 부모 노드 parent node, 행동 action, 비용 path cost에 대한 정보를 담고 있는 데이터 구조라고 볼 수 있습니다.
    2) 노드 가져오기: Frontier에서 마지막 노드를 추출합니다. (stack 구조)
    3) 솔루션 확인과 리턴: 만약 2)의 노드가 목표하는 노드라면 검색과정을 종료하고 솔루션을 리턴합니다.
    4) 노드 추가: Explored set에 노드를 추가합니다.
    5) Frontier 확장: Frontier에 하위 노드(child node)를 추가합니다. 이 때 하위 노드가 frontier와 explored set에 존재하는지 확인합니다. 만약 존재한다면 하위 노드는 추가할 수 없습니다.



 위 과정에서 어떤 특징을 찾아볼 수 있을까요?
 검색 과정에서 마지막 노드(F)를 만날 때까지 계속 하위 노드를 찾아갑니다. 마지막 노드(F)에 다다르면 목표 노드(E)와 일치하는지 비교합니다. 만약 목표 노드와 일치하지 않는다면 다시 마지막 분기 지점(B)으로 돌아가서 같은 방식으로 검색을 이어갑니다. 다시 마지막 노드(E)에 다다르면 목표 노드(E)와 일치하는지 비교합니다. 일치한다면 검색 과정을 종료합니다.
 이처럼 가장 깊은 단계 노드까지 확장하며 검색하는 방식이 DFS Depth First Search입니다. DFS는 stack 구조를 사용하여 노드를 검색합니다.

 노드의 수를 V Vertex, 연결선의 수를 E Edge라고 할 때, DFS의 공간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다. 시간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다.

 DFS의 장, 단점은 아래와 같습니다.
  • ⊙ 장점
  • ▷ BFS에 비해 작은 저장공간을 필요로 합니다. 지나간 모든 노드를 저장할 필요 없이 분기점의 노드들만 들어갑니다.
  • ▷ 목표 노드가 깊은 단계에 존재할수록 BFS보다 빠릅니다.
  • ⊙ 단점
  • ▷ 목표 노드가 아닌 경로의 깊이가 깊을수록 많이 시간을 소비합니다.
  • ▷ 결과 솔루션이 최단 경로가 아닐 수도 있습니다. DFS는 목표 노드를 만나는 순간 종료되므로 항상 최단 경로를 찾는 것은 아닙니다.

Algorithm: DFS Code

 DFS를 미로찾기 문제에 적용해 보겠습니다.



 'Node' 클래스는 노드 객체를 생성합니다. 노드는 에이전트의 상태, 부모 노드, 그리고 행동에 대한 정보를 가지고 있습니다.



 DFS는 stack 구조를 사용하여 노드를 검색합니다.
 'StackFrontier()' 클래스는 우선 비어있는 리스트 형태의 frontier 객체를 생성합니다.
 'add' 함수는 frontier에 노드를 추가합니다. 다음 단계 노드(자식 노드)를 frontier에 추가합니다.
 'contains_state' 함수는 노드가 이미 frontier에 들어있는지 검사합니다.
 'empty' 함수는 frontier에 담긴 노드 수가 0인지 확인합니다. Frontier에 더이상 가져올 노드가 없는지 확인하는 함수입니다.
 'remove' 함수가 본 클래스의 핵심입니다. DFS는 stack 구조를 사용합니다. 따라서 frontier의 가장 마지막 위치에 존재하는 노드를 가져옵니다.



 파일로부터 미로찾기 문제를 읽고 시작(S)에서 끝(E)까지 경로를 찾는 과정입니다.
 'Maze()' 클래스는 미로찾기 문제가 담긴 파일을 읽습니다. 시작 위치(S), 종료 위치(E), 벽, 그리고 길을 파악하여 rrow * ccolumn 크기의 행렬로 정리합니다.
 'print_out' 함수는 미로와 솔루션을 출력합니다.
 'neighbors' 함수는 현재 노드에서 이동 가능한 노드로의 방향과 그 좌표를 확인하고 모두 리턴합니다.
 'solve' 함수는 솔루션을 발견하거나 더이상 frontier에 검색할 노드가 남아있지 않을 때까지 검색 과정을 반복 수행합니다.
 'output_image' 함수는 미로와 발견한 솔루션을 이미지 파일로 출력해주는 역할을 합니다.

 전체 코드와 예제 파일은 이 곳에서 확인할 수 있습니다.

Algorithm: DFS Example

 실제 미로 문제 파일을 입력받아 코드가 솔루션을 찾아내는 과정을 실행해 보겠습니다.



 하지만 DFS의 단점으로 알아봤던 것처럼 항상 최적의 솔루션을 찾는 것은 아닙니다. 위 예시에서도 maze3.txt의 경우 가까운 길을 두고 먼 길을 돌아서 찾아간 것을 볼 수 있습니다. 그렇다면 이런 경우 최적의 솔루션을 어떻게 찾을 수 있을까요? 바로 BFS Breathe First Search를 사용하는 것입니다.

Two reasons for that

  1. To reduce gap between sample variance and population variance
    ( empirical reason )
    1. "1/n" version is the maximum likelihood estimate of the population variance, however, it is also mathematically biased
    2. sample variance is usually smaller than the population variance
      → estimation of the population variance is getting bigger than real
    3. to reduce gap using "1/n-1" convention ( provides an unbiased estimate )
    4. why not n-2 ?
      1. related to degree of freedom, that is n-1
  2. To match both expectation of sample variances and population variance
    ( mathematical reason )
    1. let,
      : sample size
      : sample mean
      : sample variance
      : population mean
      : population variance
    2. then, figure out following is true
    3. first,







    4. as here,



Using an output of precedent command as an argument of following command

xargs is a great command that reads streams of data from standard input, then generates and executes command lines

  1. to print all vcf files in specific path
    echo `pwd` | cut -d'/' -f1-7 | xargs -I{} find {} -name '*.vcf'
  2. to know the number of lines/words/characters in specific file
    ls * | xargs -IFILE grep -vc '^#' FILE
  3. to count the number of all variants of vcf
    ls * | xargs -IFILE echo FILE | xargs grep -vc '^#' FILE