0. Abstract

• Structural variation (SV)을 찾는 것은 genome interpretation에 굉장히 중요하지만, 현재 기술의 한계로 인해 어렵다.
• Ensemble algorithm과 새로 등장하는 시퀀싱 기술을 바탕으로 하는 detection method는 수천개의 SV를 발견하는데 도움을 줬으며, 질병과의 연관성을 밝히는데 많은 도움을 주고 있다.
• SV는 종류와 크기가 다양하고, 변이를 발굴하는 genomic platform 마다 detection 편향이 있기에, multiplatform discovery 방식으로 넓은 변이 스펙트럼을 잡아야 한다.
• 이 논문에서는 SV를 찾는 최신 방법들을 알아볼 것이다.

1. Introduction

• High-throughput sequencing (HTS) = NGS의 발전 덕분에 SNV, small indels(<50bp), 그리고 SV가 개개인마다 다르다는 것을 확인할 수 있었다.
• SV 는 종류와 크기가 다양하고, 분류를 크게 하면 unbalanced SV (=CNV: deletions, duplications, insertions) 그리고 balanced된 (inversion, inter/intrachromosomal translocations)로 나누어진다.
• 이뿐만 아니라, mobile element insertion, multi-allelic CNVs, segmental duplication 그리고 complex rearrangements.
• SV detection을 위해 널리 쓰이고 있는 툴과 알고리즘은 주로 short read signature 를 이용해 reference genome와 비교를 함으로써 SV의 존재를 유추를 한다. Short-read 접근 방식은 SNV를 처리하는데 매우 효과적이지만, 한정된 sequence와 insert size의 단점을 가진 standard _short-read HTS_의 한계를 뛰어넘지는 못한다.
• SV는 SNV와 다르게 multiple short reads를 다루다 보니, computational inference가 요구 되고, SNV 발견하는 발전 속도에 많이 뒤쳐져 있는 상황이다.
• 이를 극복하기 위해, flow cell, advanced microfluidics, 그리고 protein pore를 이용한 새로운 시퀀싱 기술들이 많아졌고, 이로 인해 기존에는 잡지 못했던 SV들을 발견하기 시작했다.
• 이번 논문에서는 기존의 short-read approach의 한계를 극복할 수 있는 다양한 알고리즘과 신규 기술들을 소개할 것

1-Vocab. Introduction 용어

• Structural variations (SV) : Sequence variants >50 bp in size. Complex rearrangements: 여러 종류의 SV들이 합쳐져 있는 복잡한 형태
• Read signatures: Specific marks that result from reads that map discordantly to the reference genome
• Short-read HTS: Standard sequencing where libraries are fragmented to ~600-800 bp in length.Two ends are sequenced ~100-250 bp with an unsequenced insert size of ~100-600 bp.
• Flow cell: Glass slides containing fluidic channels for sequencing reactions to occur.
• Microfluidics: Devices that precisely manipulate and control small amounts of fluids.

2. Ensemble Algorithms

• 시퀀싱 기반 SV detection은 sample read와 reference genome과의 맵핑 차이로 생기는 signature 정보를 사용한다.
• 4개의 주요 방식: read-pair, read-depth, split-read, de novo assembly
• 초기의 _SV caller_들은 (BreakDancer, CNVnator, etc.) 위의 4가지 방식 중 하나만 사용을 해서 만들었었다. 그후로, Hybrid-signature algorithm들은 위의 4가지 방식들 중 여러개를 조합해서 sensitivity를 늘릴 수 있었다 (DELLY, LUMPY, Manta)
• 그럼에도 불구하고, 아직도 모든 범위의 SV를 잡을 수 있는 ‘하나'의 caller는 없다. 한 가지의 방법은, 동일한 시퀀스에 대해서 여러개의 알고리즘을 사용한 후, 결과를 통합해서 unified call set을 만드는 것. 이런 방법을 ensemble algorithm 이라고 이번 논문에서 지칭한다.
• 여러개의 알고리즘을 합치고 나서, 중복으로 call 된 SV에 대해서는 필터를 거칠 필요가 있는데, 이 필터할 요소들은 breakpoint confidence overlap, breakpoint distances, false-discovery rate (FDR) cut-off thresholds, read-signature prioritization (split reads > read pair > read depth), caller concordance, signature thresholds와 같은 것을 포함한다.
• 그리고 coordinate overlap 이라는 요소도 있다. 이 수치를 조절하면서 sensitivity/FDR를 조절한다.

• 이런 ensemble algorithm을 표준화 하기 위한 stand-alone tool들이 여러개 있다
• 예시로:
  • SpeedSeq는 LUMPY + CNVnator로 SR, PR, RD로 뭉쳐서 SVTyper로 validation해줌
  • HugeSeq, iSVP, Parliament2, SVMerge는 intersect by coordinate overlap으로 call이 여러개의 caller로 나왔는지 요구한다.
  • MetaSV는 union만을 가져오고, caller overlap을 요구하지 않는다
  • SVmerge와 MetaSV는 call을 local reassembly로 검증을 하고, MetaSV는 resolution이 더 높은 signature를 우선시한다.
  • Parliament2 allows users to decide on a combination of six short-read algorithms before merging calls with SURVIVOR and genotyping with SVTyper.
• 이렇게 연구자들은 이제 Ensemble 알고리즘으로 단순한 overlap을 넘어 세밀하게 설정을 해 precision을 높이고자 한다 (이 중, 실제 truth set을 만들어서 이에 바탕으로 진행을 많이 함)

2-1. Population-scale SV detection

• Ensemble algorithm 방법으로 진행한 population study에서 SV chracterization이 활발하게 진행되었음
• 1000 Genomes Project (1KGP) 에서는 19개의 algorithm을 사용해, 총 51개의 SV hotspot을 찾아 내었고, phase 3에서는 총 2,504명의 샘플에 대한 분석을 완료해, 가장 comprehensive하고 diverse한 reference set을 생성한 것으로 알려져 있다. 그러나 coverage가 낮은 (~6-7x) 시퀀싱으로 진행을 해서, rare variants를 찾기에는 어려움이 있었다.
• 이를 시작으로, 이제 점점 더 큰 규모의 study들이 진행이 되면서 SV에 대한 데이터는 많이 축적되고 있다.

2-2. Limitations

• 워낙 다양한 algorithm을 쓰다보니, 프로젝트마다 사용한 coverage가 굉장히 들쑥날쑥 (3x ~ 90x)하기 때문에 ad hoc/heuristic 하게 필터링을 하면서 결과에 대한 sensitivity나 결과 자체에 영향을 많이 준다.
• 그리고 어떤 알고리즘을 쓰는지, test로 사용하는 benchmark call을 어떤걸 쓰는지, 필터는 어떻게 하는지에 따라 성능이 천지차이다.
• 앞서 말한 Stand-alone ensemble 툴들은 simple overlap 만들 고려하기 때문에 굉장히 immature하고, 이 중에서도 벤치마킹할 수 있는 데이터셋이 없어 통합하기가 쉽지 않다.
• 이래서, ensemble algorithm 영역에서도 다 통용될 수 있는 벤치마크 데이터와 방법론이 생기는 것이 매우 중요할 것

2-Vocab. Ensemble algorithms 용어

• SV caller: algorithm designed to detect SV. Each putative SV detected by a caller is an individual ‘call’
• Ensemble algorithm: A detection method that combines the resulting call sets from multiple independent algorithms
• Coordinate overlap: Number of base pairs that are identical between two different variant calls

3. Emerging genomic technologies

• Short read의 한계를 넘기 위해 새로운 기술들이 많이 등장함.

3-1. Connected-molecule strategies:

• Long-insert short-read libraries와 비슷하다. _Sequence coverage_와 high _physical coverage_에 대한 trade-off를 조절하며 크고 작은 변이들을 추출한다.

  Linked reads

  • Pooled-clone sequencing과 Illumina의 synthetic long reads와 같이, short-read sequences들로 long-range information을 유추하는 방식이다.
  • 현재는 10x Genomics Linked-Reads (LR) 플랫폼이 가장 많이 쓰이는 synthetic long-read platform이다.
  • Short-read sequencing을 진행하기 전에, short-read fragment 앞에 partition/barcode를 넣어서, 바코드 정보를 토대로 long-range information을 쌓을 수 있는 방식 (10x Genomics 설명 링크: 링크)
  • 같은 가격으로 physical coverage를 높일 수 있다보니 SV를 발견하는데 도움이 되고, haplotype phasing에도 도움이 많이 된다.
  • Detection methods (Long Ranger, GROC-SVs) 즉, SV를 탐지하는 방법들은 read cloud를 주로 사용하는데, 이 read cloud는 short read의 cluster라고 생각하면 된다. Read cloud는 두 가지를 고려한다: density of overlapping barcodes (바코드가 확 많아지거나, 확 줄으면 breakpoint를 유추할 수 있기 때문), 그리고 distant genomic loci that share more barcode overlap.
  • 장점: 바코딩으로 인해 큰 SV에 대해서도 visual interpretation이 효과적.
  • Single-molecule approach와 비교했을 때 비슷한 양의 deletion 검출, 하지만 insertion에 대해서는 결과에 대한 차이가 있음. 여기에 대한 이유는: linked reads는 coverage drawback이 있기 때문이다. Read cloud에 있는 그 어느 molecule도 DNA fragment의 complete coverage가 없기 때문에 read pair 간의 gap이 많아서 repetitive region이나 insertion에서 mapping 성능이 매우 떨어질 것이다.

    Strand-seq

  • Strand-seq independently sequences template DNA strands by incorporating bromodeoxyuridine into the non-template strand during replication.
  • As libraries only contain independent parental strands, Strand-seq is especially suited for haplotype phasing. The inherent directionality enables highly efficient detection of inversions.
  • 완벽히 이해한건 모르겠지만, BRdU가 parent strand에 붙게 되면서 다른 strand는 directionality가 보장되는 형태로 만들어진다. 이게 SV detection에서는 inversion을 효과적으로 잡을 수 있게 되고, 다른 SV 종류는 read depth로 탐지가 가능해진다.
  • 단점으로는 enzymatic clean-up step이 많아서, 결과적으로 sequence coverage를 굉장히 낮추기 때문에 작은 SV를 찾기 힘들다..

    Hi-C

  • Hi-C는 crosslinked chromatin을 시퀀싱함으로서 3D 공간에서 proximity를 볼 수 있는 방법이다.
  • Hi-C read pair는 megabase 단위로도 설정이 가능하기 때문에 large SV 포착 가능
  • 하지만 linear genome 상에서 몇 kb가 떨어져 있어서 resolution 자체에 한계가 있다 + coverage도 낮음
  • Interactions between proximal loci are shown in the diagonal, diagonal에서 떨어져 있으면 long-range interactions.
  • 3D 구조로 SV를 탐지하고 설명하는 것은 아직 많은 연구가 필요하기 때문에, Hi-C의 결과를 reliable하게 사용하려면 아직 멀었다

3-2. Single-molecule strategies

Single-molecule real-time sequencing (SMRT)

• PacBio’s SMRT sequencing leverages a stationary polymerase attached to the bottom of a nano-sized well and passages single DNA strands through the enzyme to produce long reads that significantly improve unambiguous mappability across the genome.
• SMRT 데이터로 SV를 찾기 위한 알고리즘들은 intra-read와 inter-read signature를 사용한다.
• Intra-read signature는 SV를 직접적으로 찾을 수 있다 (missing sequence = deletion, soft-clip = insertion).
• Inter-read는 여러개의 read를 사용하며, orientation, location, size의 불일치를 토대로 SV를 찾는다
• Signature를 포착한 후에, caller들은 비슷한 signature들끼리 뭉쳐서 SV를 찾는다. (Caller 예시: CORGi, PBHoney, pbsv, Sniffles, SMRT-SV, SVIM 등등)
• 아직까지는 비싼 가격, input으로 요구하는 많은 양의 DNA 때문에 short-read study보다는 적은 수의 genome에서 실행이 됐었다.
• 비록 _base-calling error rate_가 short-read 방법보다는 높지만, 이는 coverage를 높이거나, _circular consensus sequencing_을 사용하면 나아짐. SMRT coverage를 높이면 더 정확해지지만, enzyme degradation으로 인해 read length가 줄어든다 - 그래서 그 trade-off threshold를 잘 정해야함.
• (...더 많은 내용) 정리 하자면, long-read technology는 예전에 찾지 못했던 SV들을 대량으로 검출하고 있음

Nanopore sequencing

• Nanopore sequencing 기반 SV 탐지 알고리즘은 아직 시작된지 별로 안 됐지만, ONT (Oxford Nanopore Technology) Sequencing을 통해 점점 접근성이 좋아지고 있다.
• Nanopore Sequencing은 single-stranded DNA가 protein pore를 통과하면서 고유의 base간의 전류 차이로 DNA sequence를 인식하는 방식이다.
• Nanopore Sequencing도 single-molecule sequencing을 기반으로 하기 때문에 signature는 PacBio 데이터와 굉장히 유사하다.
• 대표적인 caller로는 NanoSV, Picky, Sniffle, SVIM. 하지만 뒤의 3개는 PacBio 데이터에서도 calling이 가능하다.
• PacBio와 비교했을 때 Nanopore에서만 발견되는 small deletion이 굉장히 많다. 하지만 이 small deletion들은 repeat region과 base-calling error에서 일어나는 것을 보아 small SV를 탐지하는데 굉장히 취약하다.
• ONT는 improved read length, lower adaption cost, higher throughput의 장점이 있지만, 위에서 말한대로 error rate가 너무 높아 specificity가 낮은 (특히 small SV에서) 약점이 있다.

Optical mapping

• Sequencing 기반 기술의 대안으로, Optical mapping은 single DNA strand에 nicking endonuclease를 마킹을 하면서 genome map이라는 physical map을 생성한다. 그리고 그 찍힌 map을 관찰하며 SV를 탐지한다
• Restriction enzyme site에 의존도가 있어서, sequence 자체를 만들지 못하고, 고로 base-pair resolution이 없는 대신 breakpoint estimation만 가능하다.
• 그래서 대부분 optical mapping은 큰 SV를 genome map으로 찾고, 작은 SV들은 short-read sequencing을 이용
• 에러가 굉장히 많고 해상도도 좋지는 않지만, amplification-free하고 HTS보다 훨씬 싸다 (60x coverage)에서도, 그래서 대규모 코호트 스터디에서는 경제적인 선택이 된다.

3-3. Multiplatform discovery

• 그 어느 기술도 깊고 넓은 종류의 SV를 잡을 수 없기에, 여러 플랫폼을 합쳐서 사용하는 방법도 등장을 한다.
• Short reads는 base-calling accuracy 가 좋기 때문에 long read들의 error를 잡는 역할을 하고 (“polishing”이라고 한다), 그리고 좀 더 최신 기술들은 좀 더 규모가 크고 복잡한 구조들은 잡는데 사용.
• 여기에 대한 실용적인 예로: Short-read sequencing으로 coverage를 높게 잡고 (>30x) + single-molecule sequencing으로는 coverage를 낮게 잡아서 (~10x), 경제적이면서 sensitivity를 높이는 선택을 할 수 있다.
• 그래서 각자 요구에 맞게 구성을 하면 된다.
• Genome assembly도 여러 개의 플랫폼을 합쳐서 사용하기도 함 (hybrid assembly)
• 여러 기술을 통합하는 Ensemble algorithm 방식이랑 똑같다.

3-Vocab. Emerging genomic technologies 용어

• Connected-molecule strategies: Genomic methods that connect shorter reads of a DNA molecule together
• Sequence coverage: The avg. number of times a given locus is covered by a sequence read
• Physical coverage: The avg. number of times a given locus is covered by the cumulative length of the reads, including unsequenced inserts.
• Base-calling error: Errors in determining the respective nucleotide from raw signals during sequencing
• Circular consensus sequencing : SMRT sequencing method that improves accuracy through multiples passes of template molecule
• Hybrid Assembly : Genome assembly that leverages sequencing data from multiple platforms to reconstruct the original sequence

4. Integrating SVs with biological information

• 기술적인 발전에도 불구하고 아직은 이 변이들의 functional consequence가 어떻게 되는지에 대한 해석이 불가능하다
• 이제는 gene expression, epigenetics, 3D genome structure와 같은 정보로 변이 해석 시도가 시작되고 있음
• -최근 연구들에 의하면 SV의 gene expression 영향이 SNV/indel에 비해 53배까지 컸다는 것도 밝혔고 SV의 functionally 큰 영향을 보여준다.
• 좀 더 holistically하게 이해를 하려면 여러 biological context에서의 데이터를 응용하면 functional effect 해석이 가능해진다

5. Conclusions

• 기술의 발전과 방법론의 발전으로 인해 SV에 대한 지식도 넓어졌다.
• 이제는 Human genome에 약 >20,000개의 SV가 있는 것으로 추정이 되고 (대부분이 short read로는 포착할 수 없었던 영역이라 더 의미가 있다)
• Detection 자체도 매우 중요하지만, 이 SV들이 어떤 영향을 (functional effect) 줄지에 대한 방법도 매우 중요하다. 그렇기 때문에 이 interpretation에 대한 발전도 동시에 이루어져야 한다.

0. Abstract

• Structural Variation (SV)은 우연의 현상이라고 여겨져 왔었으나, 이제는 interindividual genetic variation의 가장 큰 원인으로 여겨진다.
• Phenotypic variation과 disease에도 영향을 크게 끼치는 것으로 알려짐
• 이번 논문에서는 SV에 대한 간단한 소개, 역사, 그리고 SV를 detect하는 여러 방법들에 대한 소개

1. Brief Introduction

• SV is generally defined as a region of DNA that shows a change in copy number (deletions, insertions, duplications), orientation (inversions), or chromosomal location (translocations) between individuals
• SV can be balanced, with no loss or gain of genetic material, such as inversions of genetic fragments or translocations of a stretch of DNA within or between chromosomes.
• SV can be unbalanced, where a part of the genome is lost or duplicated, which is termed copy number variation (CNV). (ex: Chromosomal aneuploidies would be an extreme case of unbalanced SV)

2. History of SV

• Genomic SV의 존재 자체는 예전부터 널리 알려져 있었다. (karyotyping과 같이 cytogenetic level에서 확인을 하면서)
  • Drosophila 에서 일어난 gene duplication은 무려 1936년에 이미 확인 되었었다.
  • 하지만, 현미경으로도 (육안으로도) 확인이 가능한 variation은 굉장히 드물었고 왠만한 genetic variation은 주로 SNPs, indels, repetitive elements로 이루어졌을거라 생각해서 별로 중요하게 여기지는 않았다.
• 10년 전 쯤 (논문 기준으로 2005년), BAC array-comparative genomic hybridization (array-CGH)와 ROMA 기술의 발전으로 인해 첫 genome SV 분석이 가능해졌다.
  • 이를 바탕으로 한 2개의 스터디 (Sebat, et al, Iafrate, et al)에서 intermediate size SV (karyotype에서 확인 불가능)이 상당한 양의 genetic variation을 가지고 있음에도 불구하고 아직 밝혀진 사실이 거의 없다라고 보여줌.
• 또한, 증상적으로 (phenotypically) 건강한 사람들에게서도 common한 large CNV들도 많고, 이런 변이들도 gene dosage, 즉 유전병에도 영향을 줄 수 있다는 것을 밝히게 되면서, genetic analysis의 새로운 챕터를 열게 되었음.
• Rare SV와 연관되어 있는 질병은 꽤 많다: IRGM gene-Crohn’s disease / LCE gene-psoriasis / SNCA gene - Parkinson
• 그렇다고, 모든 SV가 damaging한 phenotype과 관련이 있는 것은 아니고, 아주 일부만 질병과 연관되어 있다. 그런 면에서 SV가 아직 밝혀지지 않은 질병의 원인을 100% 찾는데는 힘들 것. (SV-disease association에 대한 추가 논문)
• 최근 몇년 동안 SV와 breakpoint에 대한 지식은 NGS 기술과 알고리즘의 발전으로 인해 더 풍부해졌다.

• SV 정보를 축적하기 위한 여러 프로젝트들이 진행이 되고 있다:
  • Database of Genomic Variants (DGV)
  • InvFESt project - predictions on human polymorphic inversions

3. Types of SV

• 이 논문에서 다룰 SV의 주요 종류들은 다음과 같다:
• Translocation: DNA segment가 intra-inter chromosomally 이동. Genetic material의 gain/loss 없음
• Inversion: DNA segment의 orientation이 reverse된 경우 (centromere가 껴있으면 pericentric, else: paracentric)
• Insertion: 새로운 서열의 생성
• CNV: DNA segment가 variable number 만큼 복사 되었을 때
• Deletion: loss of genetic material
• Duplication: tandem/interspersed duplication

4. Generation of structural variants

• SV가 일어날 수 있는 변이 메커니즘들이 있다 (meiotically and mitotically)
• Recombination error (e.g. non-allelic homologous recombination; NAHR); DNA break repair (e.g. non-homologous end joining; NHEJ, microhomology-mediated break-induced replication; MMBIR); Errors in replication (fork stalling and template switching; FoSTeS) 등등..
• (자세한건 분자세포생물학 책 정독 ㄱㄱ)

5. Detection of SV

• SV 종류들 중에서 가장 지식이 많은 분야는 Copy Number와 관련되어 있는 변이들이다. (이유: 지금의 기술로 잘 찾아짐)
• 2004년에 array-CGH로 인해 SV 분석의 분야를 활성화 시켰다. (array-CGH는 CNV 탐색에 좋은 기법이다)
  • Array-CGH: Analysis of intensity ratios of the hybridization of two differentially dyed DNAs against the same target oligonucleotides. 단점: Detects imbalances between two individual genomes, and thus cannot provide an absolute copy number. Also blind to balanced SV events.
• 몇 년 뒤에, SNP-array 데이터를 이용한 CNV 추출하는 알고리즘들이 생겼다 이 알고리즘들은 (PennCNV, QuantiSNP, Birdsuite etc) SNP intensity 정보를 이용하여 시도를 했으나, array-CGH 보다 CNV call을 못함
  • 장점: array-CGH에 비해 balanced SV의 존재를 유추할 수 있음
• 더 최근에는 이제 NGS의 발전으로 인해 genomic SV의 발견이 좀 더 섬세해질 수 있었다.
  • NGS 초기에는 single read로 진행이 되었지만, 기술의 발전으로 paired-end reads가 더 흔해졌다.
  • Paired-end reads는 reference sequence에 더 align이 잘되고, SV 탐지에 추가적인 정보를 제공해준다
  • 이로 인해 small CNV 탐지도 가능해졌고, breakpoints들의 다양한 characterization이 가능해졌다.
• 하지만, 최고의 성능을 위한 최적의 알고리즘을 아직도 찾는 과정이다.
  • 주로 이 4개의 전략에 기반을 둔다:
  • Read Depth (RD): Read Depth analysis는 주로 CNV를 발견한다. RD는 주어진 인터벌에서의 read density을 바탕으로 검색. 비록 RD 분석이 유일하게 copy-number를 정확하게 예측할 수 있는 sequencing-based 방법이지만, breakpoint 해상도가 낮고, sequence coverage에 많이 의존한다. 또한, PCR-induced coverage bias와 balanced SV와 같은 inversion, translocation을 찾지 못한다. (예시 알고리즘: CNVnator)
  • Paired read (PR): involves the identification of clusters of aberrantly mapped read pairs, suggesting the presence of SV breakpoints between the reads. 이 mapped paired-reads의 정렬이 다를 경우 다양한 시나리오에 대해서 다양한 종류의 SV를 유추해낼 수 있다. (아래의 Figure의 B.) 하지만, 단점들은: breakpoint의 resolution은 library의 insert size mean, std, coverage에 영향을 받을 것이고, library의 insert size에 따라 insertion을 못 잡을 수도 있다. (예시 툴: Breakdancer)
  • Split Reads (SR) + Clip Reads (CR): Aimed at direct identification of sequence reads that span the breakpoints of SV. Provides single nucleotide-level resolution. SR 방법은 NGD 데이터에서는 short read를 align하는데의 어려움으로 인한 한계가 있다. Gap이 클수록 align을 하기가 더 어려움. (예시 툴: Socrates)
  • De novo sequence assembly (AS): enables the fine-scale discovery of SVs, including novel (non-reference) sequence insertions, as they do not rely on a reference sequence. Computational cost가 높고 시간 소모와 assembly 에러가 자주 일어날 수 있지만, targeted sequencing assembly를 하는데 굉장히 가치가 높다. (예시 툴: TIGRA)

• 위에서 언급한 다양한 방법들은 고유한 장단점이 있지만, 그 어느 방법은 SV의 full spectrum을 잡지 못한다.
• 그래서 조합으로 사용하는 경우가 많아짐:
  • RD와 PR을 합쳐 CNV를 더 잘 잡는 툴들: inGAP-sv, CNVer, VariationHunter etc.
  • PR + SR : Pindel, PRISM, Delly
  • 그러나, 조합으로 만든 3개의 알고리즘으로 잡은 SV들은 크게 겹치지가 않고, 1000 Genome Project에서 검토를 한 결과, 각 방법론은 sensitivity와 specificity가 매우 다양하게 측정되었음. 그나마 GenomeSTRIP이라는 툴이 나았다 (low false discovery rate 때문에). False discovery rate를 더 줄이기 위해 forestSV라는걸 만들었고 (RD + PR 조합).

6. Conclusion & Key points

• Structure variation is a common form of inter-individual genetic variation
• Balanced SV poses bigger challenges and has been less studied than unbalanced forms
• Structural variants are mostly discovered through array-CGH, intensity analysis from SNP arrays and read-pair and RD analysis of high-throughput sequencing data
• SV can be generated by errors in recombination, replication or by erroneous break repair mechanisms, arising both mitotically and meiotically.

개인 Comment:

• SV의 간단한 소개, 왜 일어나는지, 그리고 이를 탐지하기 위한 역사를 알기에 간단하게 정리된 리뷰 논문이였다

0. Abstract

• Text classification에서의 Feature Selection에 대한 리뷰 논문
• Representation 방법, Classifier 종류, 그리고 네 가지 Feature Selection 모델 소개

1. Introduction

• 기술의 발전으로 많은 양의 텍스트 정보가 돌아다니고 있다. (CNN 뉴스, 트위터 트윗, 아마존 고객 리뷰 등등)
• 수많은 양의 텍스트 중에서 내가 관심 있는 주제로만 읽고 싶어하고 싶을 땐 text categorization으로 분류하기
• 하지만 다양한 단어들이 등장하는 데이터에서 모든 단어들로 텍스트 분류를 하겠다고 하면, 당연히 성능이 낮죠
• 그래서 이번 리뷰 페이퍼에서는 최고의 성능을 위한 여러 가지 방법과 기본 지식을 소개하겠다~

2. Text Classification

• 정의: 문서에 사전 정의된 레이블/카테고리를 부여해주는 것
• 미리 모은 문서 {D}를 이용해 분류기 {T}를 만든다

2.1 Document Representation

• 가장 유명한 document representation은 bag-of-words model (문서 d에 단어 s가 빈도 f번 나왔는지 표현)
• bag-of-words에서 단어에 좀 더 weight를 부여하고 싶으면 TF-IDF weighting scheme을 넣을 수 있음
• 문서의 단어/feature 리스트를 설정하는데 두 가지 방법: universal dictionary method, local dictionary method Universal method: 모든 문서에 사용할 feature를 생성 Local method: 문서 label 클래스에 특정한 dictionary를 지정

2.2. Similarity between documents

• 유사도 계산은 document clustering, classification, data mining, information retrieval에 매우 중요

• 대표적인 유사도 계산 방법은 다음의 예시가 있다: a) Euclidean distance: L2 metric으로 좌표간 거리 계산. 하지만 고차원 영역에서는 Euclidean distance가 다 비슷비슷해져서 굉장히 성능이 낮음 b) Cosine similarity: Text categorization에서 자주 사용. 주로 문서 벡터를 미리 normalize하고 사용 c) Jaccard coefficient: 시작은 두 ecological species 간의 유사도를 구하기 위해서 사용 되었으나, 이제는 두 집합이 얼마나 비슷한지 계산을 위해 많이 쓰이는 중 d) Dice coefficient: Jaccard coefficient와 비슷한 측정 방법

• 어떤 연구자들은 Information theory 의 시선에서 유사도를 측정해야 한다고 주장. 그래서 다음과 같은 기법: e) IT-Sim: i.e. Information-theoretic measure. 메인 아이디어는, 두 물체 간의 유사도는 = 그 물체가 소유하고 있는 공통적인 정보 + 다른 정보의 관한 주제. 성능은 매우 좋으나, computational cost가 크다 f) SMTP: 같은 information-theory 기반 측정법. 다음의 세가지 정보를 사용: 두 문서에 등장하는 feature, 하나의 문서에만 등장하는 feature, 그리고 두 문서에서도 등장하지 않는 feature. SMTP이 IT-Sim보다 성능이 좋다

• 문서 구조에 대한 정보 (즉, 문서 상에서의 단어의 분포도와 같은 정보)는 사용하지 않았는데, 그 정보도 고려해야하지 않나. 문서마다 단어에 대한 분포도는 다른데, 그 정보도 고려해야 한다: g) EMD-based: 우선 문서를 subtopic으로 분해한 후에, subtopic에 따라서 Earth Mover’s Distance로 유사도를 계산 h) K-L divergence-based: 두 단어의 분포도에 대한 발산을 바탕으로 유사도 계산

2.3 Classifiers for text classification

• 문서 분류기
• 1. kNN (k-Nearest Neighbor) classification 정의한 거리/유사도 측정의 기준으로 가까운 문서들을 묶어서 분류하는 방법. 사용하기 간단하고 실용성이 좋다, 하지만 computational cost가 높다
• 2. Naive Bayes (NB) 특정 feature의 값은 다른 feature와 independent하다는 가정에 사용 두 가지 NB 분류기가 있는데, 하나는 multivariate Bernoulli NB = binary vector로 문서를 표현하고 feature가 있다/없다로만 단순히 표기. 다른 하나는 multinomial NB = term frequency로 문서 표현
• 3. Linear Least Squares Fit (LLSF) Multivariate regression model. Training 문서와 그 category 간의 correlation을 스스로 학습하는 모델 결과는 word-category regression coefficient의 행렬로 반환
• 4. Decision Tree Decision Tree를 만들어 문서가 어떻게 분류가 되어야 하는지 tree대로 따라감 Accuracy에 한정해서 NB보다 성능이 잘 나오는 편
• 5. Support Vector Machines (SVMs) Structural risk minimization principle to construct an optimal hyperplane with the widest possible margin to separate a set of data points that consist of positive and negative data samples. (즉, +/-한 데이터 포인트들을 가장 잘 분리할 수 있는 hyperplane을 정의하는 모델) 텍스트 데이터는 주로 굉장히 고차원 벡터인데 SVM은 그 고차원 특성과 independent해서 잘 쓰임. 또한 굉장히 sparse한 문서 벡터에도 사용이 잘되고, 모든 feature들을 잘 사용할 수 있어서 애용되는 기법
• 6. Neural Network CNN으로 text classification해보니깐 잘 되더라~

3. Feature selection for text classification

• 다양한 분류기 (classifier)가 있음에도 불구하고, 텍스트 분류는 매우 고차원 벡터인 특성상 어려움을 겪는다.
• 또한 feature인 단어들이 noisy, less informative, redundant한 정보일 수도 있으므로 더 어려워진다.
• Feature selection은 결국 이런 불필요한, 부정확한 정보들을 추릴 수 있어야 한다
• 주로 4가지로 분류가 된다: filter model, wrapper model, embedded model, hybrid model

3.1 Filter Model

• Frequency로 필터 가능: Document Frequency (DF), TF-IDF
• Information theory로도 필터 가능: Mutual Information (MI), Information Gain (IG), Chi-squared (CHI), ECCD, PCA, correlation coefficient (CC), t-test. etc
• 아래의 테이블에 예시가 굉장히 많은데, 굉장히 단순하면서도 써볼만한 filter 방법들이 많으니, 해결하고자하는 문제에 잘 맞는 방법을 사용하는 것을 추천한다

3.2 Wrapper Model

• 분류기의 최고의 성능을 내는 Feature subset S’ 를 선별하고 고르는 작업
• 하지만 S에서 최고의 S’를 구하는데 정말 많은 자원 필요…

3.3 Embedded Model

• 우리가 아는 그 임베딩 모델

3.4 Hybrid Model

• Embedding 모델과 다르게, filter + wrapper 조합으로 feature selection하는 방법
• Filter model과 wrapper model을 같이 사용하면, 필요 없는 feature를 앞단에서 좀 제거를 하여 wrapper model의 cost가 줄을 수 있는 방식으로 진행

4. Discussion and Conclusion

• 보여준 예시 말고도 정말 다양한 기법들이 등장을 했으니, 잘 살펴보며 사용을 해보자

0. Abstract:

• 기존의 NLP 방식은 task-specific한 설정과 training from scratch 완전 백지 상태에서 부터 시작을 한다.
• 즉, 경제 기사와 정치 기사를 분류하는 모델을 만들려면, 훈련용으로 많은 양의 경제 기사와 정치 기사를 모아야 하고, 모델은 초기 백지 상태에서 시작을 해야 한다.
• 이런 방식을 대체하기 위해, 이 논문에서 Universal Language Model Fine-tuning (ULMFiT)이라는 효과적인 Transfer Learning (전이 학습) 방법을 구현했다.
• 위의 비유에 대입을 하자면, 경제/정치 기사와 별개로 다른 기사들로 미리 학습된 (pre-trained) 언어 모델을 구성한 후에, 경제/정치의 소스를 덮어서 (Fine-tuning) 모델을 만드는 방식.
• 이 방식으로 적은 양의 학습 데이터로도 훨씬 좋은 성능을 낼 수 있었다고 한다.

1. Introduction

• Transfer Learning은 이미 Computer Vision (CV) 분야에서 이미 큰 영향을 끼쳤다. 이를 바탕으로 응용해보자
• 우선 NLP에서 딥러닝 모델들이 좋은 성능을 보여주고 있지만, 이 모델들은 백지 상태에서 시작하고 많은 양의 데이터를 요구한다.
• NLP는 주로 Transductive transfer 에 초점이 맞춰져 있었다.
• Inductive transfer 에서는 pre-trained된 word embedding은 성능이 좋아서 많이 쓰임
• Pre-trained된 모델을 이용하는 것은 많은 장점을 가져오지만, NLP에서는 몇 가지 이유로 성공적으로 쓰이지 못하고 있다.
  • NLP모델은 CV 분야에 비해 모델 깊이가 얕고, 대부분은 Language Model들은 작은 데이터셋에 학습이 되어 overfit된 경향 때문에 fine-tuning을 해도 catastrophic forgetting이 자주 일어난다고 한다.
• Universal Language Model Fine-tuning (ULMFiT)로 아무 NLP 문제에 안정적인 inductive transfer learning을 제공

(* Transductive transfer vs. Inductive transfer)

• 두 학습 방식의 차이
• (참고 링크: https://towardsdatascience.com/inductive-vs-transductive-learning-e608e786f7d)

2. Related Work

• Transfer Learning in CV

  • CV 분야에서의 학습은 “general to task-specific” 하게, 첫 layer에서 general한 pre-trained 모델을 transfer하고, 뒤쪽 layer에 갈수록 task에 specific해지는 방식이다.
  • 주어진 목적에 맞는 학습 모델이 필요하면, 좀 더 general한 모델을 우선 사용해서, 학습을 시작한다는 느낌
  • 비유가 될지는 모르겠지만, 미슐랭 급 맛집을 찾아주는 모델을 만들고자하면, 식당들의 정보에 “망고 플레이트"에 등록된 식당들의 임베딩 정보를 먼저 덮어서 모델 학습을 진행한다는 느낌.
  • 하지만 요즘에는 앞단의 layer들이 아닌, 앞의 layer들은 frozen 상태로 두고, 뒤의 마지막 layer에 pretrained model을 사용하는 추세이다.

• Hypercolumns

  • Hypercolumn이라는 개념은, 다른 task에서 pre-trained된 embedding을 가져와 좀 더 추가적인 context를 넣기 위해 layer 사이사이에 껴놓는 방식이다.
  • 하지만 CV 분야에서는 end-to-end fine-tuning 방식에 의해 거의 대체된 상태

• Multi-task learning (MTL)

  • 기존 모델에 또 다른 Language Model을 추가해서 결합 학습이 되는 방식.
  • Pre-trained된 모델을 쓰는게 아니라 처음부터 학습이 되어 비효율적

• Fine-tuning

  • Pre-trained된 모델을 사용한다고 해도, 목적에 맞게 정교하게 tuning을해야하는 것이 fine-tuning이다.
  • 그럼에도 NLP 분야에서는 좋은 성능으로 fine-tuning을 하려고 해도 10k이상의 데이터를 사용해야 가능…
  • 하지만! ULMFiT는 100개의 데이터로도 SOTA 달성했다~라고 자랑

3. Universal Language Model Fine-tuning

• ULMFiT는 large general-domain corpus에 pretrain 되어 있고, target task에 fine-tune되는 방법론이다.
• “Universal”한 이유는 다음과 같다:
  1. Works across tasks varying in document size, number and label type = Domain, Task와 환경과 상관 없음
  2. Uses a single architecture and training process = 한 가지의 아키텍처 및 학습 절차
     3. Requires no custom feature engineering or preprocessing = 부가적인 Feature Engineering X
     4. Does not require additional in-domain documents or labels = 추가적인 문서 및 레이블 X
• 실험에서 사용한 Language Model은 그 당시 SOTA였던 AWD-LSTM

• ULMFiT는 다음과 같은 단계로 구성이 된다:

  1. General-domain LM pretraining

     • 문서 약 30000개와 단어 1억개로 구성된 Wikitext-103로 pretrain 진행
     • 가장 자원과 시간이 많이 소요되지만, 한 번만 실행을 하면 되고 좋은 성능을 가져올 것이기 때문에 괜춘

  2. Target task LM fine-tuning

     • Pre-trained 된 general-domain 데이터가 아무리 다양한 집군으로 이루어져 있어도, target task의 데이터는 다른 분포를 이룰 것이기 때문에 fine-tuning을 해야한다.
     • Fine-tuning은 두 가지 방법으로 진행을 한다: Discriminative fine-tuning and slanted triangular learning rates:

     -- Discriminative fine-tuning: 각 layer는 “different types of information”을 가지고 있다. (Yosinski et al., 2014) 그래서 각 layer마다 different learning rate를 사용한다. 실험적으로 확인을 해보니 마지막 layer를 fine-tuning을 하고, 앞 layer들의 learning rate을 2.6으로 나눈 값으로 설정하는게 성능이 잘 나왔다고 한다.

     -- Slanted triangular learning rates: Task-specific하게 parameter들이 잘 학습이 되기 위해서는 초반에 빨리 적합한 parameter space에 converge한 후에, 그 후에 parameter를 정밀하게 자리 잡길 학습한다.위의 설명과 같은 학습법을 위해 slanted triangular learning rate (STLR)를 사용. 처음에는 linear하게 learning rate를 높인 후에 linear하게 decay하는 방식이다.

  3. Target task classifier fine-tuning

     • 마지막으로 classifier를 fine-tuning하기 위해 pre-trained LM을 linear block 두개 (Batch normalization + dropout + ReLU activation, 그리고 확률을 내뱉기 위한 softmax)
  • 추가적인 요소들) (Concat pooling) layer의 hidden state만을 고려하면 information을 많이 잃어버릴 수도 있기 때문에, 마지막 hidden state를 모든 time step의 hidden state들의 max-pool값과 mean-pool 값을 concatenation해준다. (Gradual unfreezing) 모든 layer들을 Fine-tuning을 한 번에 하는 것보다 (이러면 catastrophic forgetting 유발할 위험이 존재) 마지막 layer부터 하나하나씩 서서히 unfreeze 하는 방식 (BPTT for Text Classification - BPT3C) Language Model은 back propagation through time (BPTT)로 학습이 된다.

4. Experiments & Results

• 6개의 잘 알려진 NLP 데이터셋을 사용. (Sentiment Analysis, Question Classification, Topic classification와 같은 주제)
• 어느 논문에서 주장하듯이 성능이 잘 나왔다고 함

5. Analysis

• 그래서 위에서 설명한 ULMFiT의 구성요소들이 어떻게 성능에 기여를 했는지 여러 조건으로 실험을 했다고 함

(i) Low-shot learning

• Transfer Learning의 큰 장점 중 하나는 작은 데이터셋으로도 좋은 성능을 낼 수 있다는 점이다. 아래의 Figure 3. 에서 보이듯이 scratch에서 쌩 모델을 만드는것보다 성능이 훨씬 좋다는 것을 확인

(ii) Impact of pretraining

• Pre-training을 한게 그래서 성능에 도움이 됐나? -> YES
• 작은 데이터셋, 큰 데이터셋에서도 도움이 됐음 (데이터셋 크기 무관하게)

(iii) Impact of LM quality, Impact of LM fine-tuning, Impact of classifier fine-tuning

• Language Model 자체를 성능이 좋은걸로 사용하면 성능이 좋아짐
• LM fine-tuning은 언급된 discriminative fine-tuning 이랑 slanted-triangular learning rates 다 쓰니깐 좋았다
• Classifier fine-tuning도 다양한 기법 사용해서 성능이 좋아짐

6. Discussion & Conclusion

• ULMFiT와 같은 Transfer Learning 기반 Language Model은 도움이 많이 될 것이다:
• 영어가 아닌 언어들은 데이터셋이 부족한데, 이 방법으로 도움이 많이 될 것
• state-of-the-art 아키텍처가 없는 NLP task에서 응용 가능할 예정
• 한정된 label data의 task도 처리 가능
• ULMFiT로 catastrophic forgetting도 방지하고, 다양한 도메인에서도 학습이 가능하게 했고, 이를 바탕으로 NLP에서도 transfer learning이 잘 사용될 수 있는 계기가 되길 바람

A.K. Uysal, S. Gunal / Information Processing and Management 50 (2014) 104–112 링크: https://www.sciencedirect.com/science/article/abs/pii/S0306457313000964

0. Abstract:

• Preprocessing is one of the key components in a typical text classification framework
• This paper aims to examine the impact of preprocessing on text classification in terms of various aspects such as classification accuracy, text domain, text language, and dimension reduction.
• 이 논문에서는 다양한 전처리 조합으로 이메일/뉴스 두 도메인 & 영어/터키어로 실험을 해봄
• 실험 결과: 다양한 조합의 전처리 기법을 적절히 섞는 것이 아예 안 쓰거나 다 쓰는 (enabling or disabling them all) 것보다 확실한 성능 개선을 보여준다.

1. Introduction:

• 전세계적으로 폭발적으로 늘어나는 전자 문서들을 정리/분류하기 위한 Text Classification
• 다양한 도메인에서 응용이 되고 있음: Topic detection, Spam E-mail Filtering, Sentiment Analysis 등등…
• 전통적인 텍스트 분류의 과정은: Preprocessing - Feature Extraction - Feature Selection - Classification
• • Preprocessing: Tokenization, Stop-word removal, lowercase conversion, stemming
• • Feature Extraction: Bag-of-words 같은 방법으로 벡터 스페이스를 구성
• • Feature Selection: Document Frequency, Chi-square와 같은 방법으로 처리
• • Classification: 다양한 분류 알고리즘 (SVM, Decision Tree, Bayesian 등등)
• 강조하고 싶은 점은, 전처리 과정도 Feature Extraction/Selection 만큼이나 중요한 과정이다

• 기존에 Preprocessing의 영향을 확인하고자 했던 연구는 굉장히 많았다.
• 스터디는 굉장히 많았으나, Table 1 의 나온 내용대로, 다 제각기 다른 환경에서 진행을 했기 때문에 스터디 별로 전처리 효과가 매우 상이하다. (성능에 좋은 영향을 주지 못했지만, 벡터의 Dimensionality를 줄일 수는 있었다…오히려 성능에 악영향을 줬다…조금 도움이 되었다…등등 결과가 매우 다양함)

• 그래서 이번 논문에서 가능한 모든 조합으로 전처리의 효과가 어떠한지 확인을 해보겠다고 함

(본 논문에서 약자를 다음과 같이 사용함) Tokenization = TK / Stop-word removal = SR / Lowercase Conversion = LC / Stemming = ST

2. Preprocessing Methods

• 그래도 처음 논문을 읽는 분들을 배려해서, 위에서 나온 전처리 기법들의 개념을 소개해준다. 나도 간단하게라도 써야겠다
• Tokenization (토큰화) : 텍스트를 단어와 같은 최소 구성 요소로 나누는 작업 (“I like cats” -> “I”, “like”, “cats”)
• Stop-words : 글에서 자주 등장하는 단어들 (예로 들면 영어에서 the, an, a, is). 너무 많이 등장해서 텍스트를 분류하는데는 큰 도움이 되지 않고 관계가 없을 것으로 예상이 되어 사전에 제거를 하는 용도로 사용한다.
• Lowercase conversion : 영어 기준으로 모든 단어들을 소문자로 변환해주기
• Stemming : 단어의 어근(?)으로 정리하는 작업. (예: running, runner -> run이라는 단어의 의미를 가진 단어로 정리)

3. Experimental Settings

• 전처리 방법, 데이터셋, Feature Selection 기법, Classification 알고리즘을 포함한 다양한 조합으로 실험
• 전처리: TK,SR,LC,ST의 2^4 = 16가지의 조합
• 데이터셋: 이메일/뉴스 도메인 & 영어/터키어의 조합
• Feature Selection: Chi-square
• Classification: SVM / 성능 측정은: Micro-F1 score

4. Experimental Work

• 다양한 시나리오에 대한 성능 요약은 아래와 같음

• 그리고 다른 연구들과 비교를 했을 때 전처리 기법의 영향 비교

• 막 우와...이걸 써야겠다...라는 느낌을 주는 설정값은 없었음.
• 결국 어떤 문제를 해결하려고 하는지, 그 문제의 환경에 따라 차이가 많이 남

5. Conclusion

• 전처리 기법도 도메인/언어나 환경에 따라 적절히 잘 사용하면 성능 개선이 도움이 되지만, 조합을 잘못하면 성능이 오히려 안 좋아질 수 있다고 확인.
• 알아서 잘 조합을 해서 사용을 해라…