shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
인간 미생물군유전체 프로젝트 (HMP)는 특히 피부, 입, 코, 소화관 및 질에 일반적으로 서식하는 미생물군유전체에 중점을 두고 인간 미생물군유전체의 유전체 염기서열 분석 프로젝트를 수행했다. 2012년에 초기 결과를 발표하면서 중요한 전환점을 맞았다.
식물상 또는 미생물상으로 널리 알려져 있지만, 이는 기술적인 용어로는 오칭이다. 식물상은 식물에 해당하고, 생물군은 특정 생태계에 있는 전체 유기체 집합을 의미하기 때문이다. 최근에는 더 적절한 용어인 미생물군유전체가 사용되고 있지만, 세균 및 기타 미생물에 대한 식물상의 뿌리 깊은 사용과 인식을 능가하지는 못했다. 두 용어 모두 다른 문헌에서 사용되고 있다.
상대적 개체수.
인체에 있는 세균 세포의 수는 약 38조 개로 추정되며, 인간 세포는 약 30조 개로 추정된다. 세균 유전자의 수는 200만 개로 추정되며, 이는 약 20,000개의 인간 유전자 수의 100배이다.
인간 미생물군유전체를 밝히는 문제는 본질적으로 세균, 진핵생물, 바이러스를 포함하는 미생물 군집의 구성원을 식별하는 것이다. 이는 주로 데옥시리보핵산(DNA) 기반 연구를 통해 이루어지며, 리보핵산(RNA), 단백질 및 대사산물 기반 연구도 수행된다. DNA 기반 미생물군유전체 연구는 일반적으로 표적화된 앰플리콘 연구 또는 최근에는 샷건 군유전체 연구로 분류될 수 있다. 전자는 특정 알려진 마커 유전자에 초점을 맞추고 주로 분류학적으로 정보를 제공하는 반면, 후자는 커뮤니티의 기능적 잠재력을 연구하는 데도 사용될 수 있는 전체 군유전체 접근 방식이다. 인간 미생물군유전체 연구에서는 존재하지만 다른 군유전체 연구에서는 존재하지 않는 과제 중 하나는 숙주 DNA가 연구에 포함되지 않도록 하는 것이다.
인간 미생물군유전체의 구성을 밝히는 것 외에도 인간 미생물군유전체에 대한 주요 질문 중 하나는 "핵심"이 있는지, 즉 대부분의 인간이 공유하는 군집의 하위 집합이 있는지 여부이다. 핵심이 있다면 특정 군집 구성을 질병 상태와 연관시킬 수 있을 것이며, 이는 HMP의 목표 중 하나이다. 인간 미생물군유전체(예: 장 미생물군유전체)는 단일 피험자 내에서도, 그리고 다른 개인 간에도 매우 가변적이라는 것이 알려져 있으며, 이는 쥐에서도 관찰되는 현상이다.
2012년 6월 13일, HMP의 주요 성과가 국립보건원 (NIH) 원장 프랜시스 콜린스에 의해 발표되었다. 이 발표는 네이처 및 공공 과학 도서관 (PLoS)의 여러 저널에 같은 날 동시 발표된 일련의 조정된 기사와 함께 이루어졌다. 유전체 염기서열 분석 기술을 사용하여 건강한 인간의 정상 미생물 구성을 매핑함으로써 HMP 연구자들은 참조 데이터베이스와 인간의 정상 미생물 변이의 경계를 설정했다. 미국 건강한 자원봉사자 242명으로부터 입, 코, 피부, 하부 장(대변), 질 등 15개(남성)에서 18개(여성) 신체 부위에서 5,000개 이상의 샘플이 수집되었다. 인간과 미생물의 모든 DNA는 DNA 염기서열 분석기로 분석되었다. 미생물 유전체 데이터는 세균 특이적인 16S 리보솜 RNA인 리보솜 RNA를 식별하여 추출되었다. 연구자들은 10,000종 이상의 미생물 종이 인간 생태계에 서식하며, 이들 중 81~99%의 속을 식별했다고 계산했다.
처리 후 분석.
통계 분석은 얻은 결과를 검증하는 데 필수적이며 (ANOVA는 그룹 간의 차이를 측정하는 데 사용될 수 있다). 그래픽 도구와 결합하면 결과는 쉽게 시각화되고 이해된다.
군유전체가 조립되면 미생물군유전체의 기능적 잠재력을 추론할 수 있다. 이러한 유형의 분석을 위한 계산적 과제는 단일 유전체에 대한 것보다 크다. 군유전체 조립기의 품질이 일반적으로 좋지 않고 많은 복구된 유전자가 불완전하거나 조각화되어 있기 때문이다. 유전자 식별 단계 후, 데이터는 상동 기관 데이터베이스에 대한 표적 유전자의 다중 정렬을 통해 기능적 주석을 수행하는 데 사용될 수 있다.
마커 유전자 분석.
프라이머를 이용하여 특정 유전 영역을 표적으로 삼아 미생물 계통학을 결정할 수 있는 기술이다. 이 유전 영역은 상세한 식별을 부여할 수 있는 고변이 영역을 특징으로 하며, PCR에 사용되는 프라이머의 결합 부위 역할을 하는 보존 영역으로 구분된다. 세균과 고세균을 특성화하는 데 주로 사용되는 유전자는 16S 리보솜 RNA 유전자이며, 곰팡이 식별은 내부 전사 간격 (ITS)에 기반한다. 이 기술은 빠르고 비용이 많이 들지 않으며 미생물 샘플의 낮은 해상도 분류를 얻을 수 있다. 이는 숙주 DNA에 오염될 수 있는 샘플에 최적이다. 프라이머 친화도는 모든 DNA 염기서열에 따라 다르며, 이는 증폭 반응 중에 편향을 초래할 수 있다. 실제로 저풍부 샘플은 과증폭 오류에 취약하다. PCR 주기 증가 시 다른 오염 미생물이 과도하게 표현되기 때문이다. 따라서 프라이머 선택 최적화는 이러한 오류를 줄이는 데 도움이 될 수 있지만, 샘플에 존재하는 미생물과 그 상대적 풍부에 대한 완전한 지식이 필요하다.
마커 유전자 분석은 프라이머 선택에 영향을 받을 수 있다. 이러한 종류의 분석에서는 잘 검증된 프로토콜(예: 지구 미생물군유전체 프로젝트에서 사용된 프로토콜)을 사용하는 것이 바람직하다. 마커 유전자 앰플리콘 분석에서 가장 먼저 할 일은 염기서열 오류를 제거하는 것이다. 많은 염기서열 분석 플랫폼은 매우 신뢰할 수 있지만, 겉보기 염기서열 다양성의 대부분은 여전히 염기서열 분석 과정 중 오류로 인해 발생한다. 이 현상을 줄이기 위한 첫 번째 접근 방식은 염기서열을 OTU로 클러스터링하는 것이다. 이 과정은 유사한 염기서열(일반적으로 97% 유사성 임계값이 채택됨)을 단일 특징으로 통합하여 추가 분석 단계에서 사용할 수 있도록 한다. 그러나 이 방법은 SNP를 단일 OTU로 클러스터링되기 때문에 폐기한다. 다른 접근 방식은 올리고타이핑으로, 16S rRNA 염기서열 분석의 위치별 정보를 포함하여 작은 뉴클레오타이드 변이를 감지하고 밀접하게 관련된 다른 분류군을 구별한다. 이러한 방법은 OTU 대신 샘플당 DNA 염기서열 및 다른 염기서열의 수량 표를 출력으로 제공한다.
분석에서 또 다른 중요한 단계는 데이터의 미생물 염기서열에 분류학적 이름을 할당하는 것이다. 이는 속 수준에서 약 80%의 정확도를 달성할 수 있는 기계 학습 접근 방식을 사용하여 수행할 수 있다. 다른 인기 있는 분석 패키지는 참조 데이터베이스에 대한 정확한 일치를 사용하여 분류학적 분류를 지원하며, 더 높은 특이성을 제공하지만 낮은 민감도를 보인다. 분류되지 않은 미생물은 세포소기관 염기서열에 대해 추가로 확인해야 한다.
계통발생 분석.
계통발생 추론을 이용하는 많은 방법은 고세균과 세균에는 16S 리보솜 RNA 유전자를, 진핵생물에는 18S 리보솜 RNA 유전자를 사용한다. 계통발생 비교 방법 (PCS)은 미생물 간의 여러 형질 비교를 기반으로 한다. 원리는 다음과 같다. 즉, 밀접하게 관련될수록 공유하는 형질 수가 많다. 일반적으로 PCS는 계통발생 일반화 최소 제곱 (PGLS) 또는 다른 통계 분석과 결합되어 더 의미 있는 결과를 얻는다. 조상 상태 재구성은 미생물군유전체 연구에서 형질이 알려지지 않은 분류군의 형질 값을 귀속시키는 데 사용된다. 이는 일반적으로 사용 가능한 데이터베이스에 의존하는 PICRUSt로 수행된다. 계통발생 변수는 연구 유형에 따라 연구자가 선택한다. 즉, 중요한 생물학적 정보가 있는 일부 변수를 선택함으로써 분석할 데이터의 차원을 줄일 수 있다.
계통발생적 거리 분석은 일반적으로 유니프락 또는 소렌센 지수(Sorensen's index), 라오의 D(Rao's D)와 같은 유사한 도구를 사용하여 서로 다른 군집 간의 차이를 정량화한다. 이 모든 방법은 수평 유전자 전달 (HGT)에 의해 부정적인 영향을 받는다. HGT는 오류를 생성하고 멀리 떨어진 종의 상관관계를 유발할 수 있기 때문이다. HGT의 부정적인 영향을 줄이는 방법은 여러 가지가 있다. 즉, 여러 유전자를 사용하거나 잠재적인 HGT 사건의 확률을 평가하는 계산 도구를 사용하는 것이다.
생태학적 네트워크 분석.
미생물 군집은 매우 복잡한 역학을 가지고 발전하며, 이는 생태계로 보고 분석될 수 있다. 미생물 간의 생태학적 상호 작용은 그 변화, 균형 및 안정성을 조절하며, 개체군 역학 모델로 표현될 수 있다.
미생물군유전체의 생태학적 특징에 대한 지속적인 연구는 빠르게 성장하고 있으며 미생물군유전체의 근본적인 특성을 이해할 수 있게 한다. 미생물 군집의 기본 규칙을 이해하는 것은 불안정한 미생물 군집과 관련된 질병을 치료하는 데 도움이 될 수 있다.
매우 기본적인 질문은 서로 다른 미생물 군집을 공유하는 인간이 동일한 기본 미생물 역학을 가지고 있는지 여부이다. 점점 더 많은 증거와 징후가 이 역학이 실제로 보편적임을 밝혀냈다. 이 질문은 과학자들이 인간 미생물 군집의 복잡한 역학을 기반으로 치료 전략을 개발할 수 있도록 하는 기본적인 단계이다.
인간 미생물 역학을 제어하기 위한 개입 전략을 개발할 때 고려해야 할 미생물 군집의 더 중요한 속성들이 있다. 미생물 군집을 제어하는 것은 매우 나쁘고 해로운 질병을 해결할 수 있다.
미생물 (예: 세균과 효모) 개체군은 몸의 여러 부위의 피부와 점막 표면에 서식한다. 이들의 역할은 정상적이고 건강한 인간 생리의 일부를 형성하지만, 만약 미생물 수가 정상 범위를 초과하거나 (종종 면역 체계가 손상되어 발생), 또는 미생물이 일반적으로 정착되지 않거나 무균 상태인 신체 부위 (예: 혈액, 하기도, 복강)에 정착하면 (예: 위생 불량 또는 부상으로 인해) 질병이 발생할 수 있다 (각각 균혈증/패혈증, 폐렴, 복막염).
인간 미생물군유전체 프로젝트는 개인이 수천 가지의 세균 유형을 보유하며, 다른 신체 부위마다 고유한 군집을 가지고 있음을 발견했다. 피부와 질 부위는 입과 장보다 다양성이 적었으며, 이들은 가장 큰 풍부도를 보였다. 특정 신체 부위의 세균 구성은 유형뿐만 아니라 풍부도에서도 사람마다 다르다. 입 전체에서 발견되는 같은 종의 세균은 여러 아형으로, 입의 뚜렷하게 다른 위치에 서식하는 것을 선호한다. 이전에 잘 이해되었다고 생각했던 인간 장의 엔테로타입조차도 분류군 경계가 모호한 광범위한 군집에서 유래한다.
인간 장에는 500종에서 1,000종의 세균이 살고 있지만, 세균 문은 몇 개에 불과하다. 바실로타문과 박테로이데테스문이 우세하지만, 프로테오박테리아, 베루코미크로비움문, 방선균문, 푸소박테리움문, 그리고 "남세균"도 존재한다.
악티노미세스 비스코수스 ("Actinomyces viscosus")와 "A. naeslundii"와 같은 여러 종류의 세균은 입에 서식하며, 치태라고 불리는 끈적한 물질의 일부를 형성한다. 이를 칫솔질로 제거하지 않으면 치석으로 굳어진다. 같은 세균은 또한 법랑질을 용해시키는 산을 분비하여 충치를 유발한다.
질 미생물군은 대부분 다양한 락토바킬루스속 종으로 구성된다. 오랫동안 이 종들 중 가장 흔한 것은 락토바킬루스 아시도필루스라고 생각되었지만, 나중에 L. 이너스가 실제로 가장 흔하며 락토바킬루스 크리스파투스가 그 뒤를 잇는 것으로 밝혀졌다. 질에서 발견되는 다른 유산균으로는 L. 젠세니, 락토바킬루스 델브루에키 및 락토바킬루스 가세리가 있다. 질 미생물군의 교란은 세균성 질염 및 칸디다증과 같은 감염을 유발할 수 있다.
고세균은 인간의 장에 존재하지만, 이 기관에 있는 방대한 종류의 세균과는 대조적으로 고세균 종의 수는 훨씬 제한적이다. 지배적인 그룹은 메테인 세균이며, 특히 메타노브레비박터 스미티아이와 메타노스파에라 스타트마나에이다. 그러나 메테인 세균에 의한 정착은 가변적이며, 인간의 약 50%만이 이러한 유기체의 쉽게 감지할 수 있는 개체군을 가지고 있다.
2007년 현재까지 병원체로 알려진 고세균의 명확한 예는 없었지만, 일부 메테인 생성 세균의 존재와 인간 치주염 사이에 관계가 제안되었다. 메테인 우세 작은창자 세균 과증식 (SIBO) 또한 주로 메테인 생성 세균, 특히 메타노브레비박터 스미티아이에 의해 발생한다.
균계, 특히 효모는 인간의 장에 존재한다. 이들 중 가장 잘 연구된 것은 칸디다 종인데, 이들이 면역결핍 및 심지어 건강한 숙주에서도 병원성을 가질 수 있기 때문이다. 효모는 피지샘에서 분비되는 기름을 섭취하는 말라세지아 종과 같이 피부에도 존재한다.
바이러스, 특히 세균성 바이러스(박테리오파지)는 다양한 신체 부위에 서식한다. 이러한 서식 부위에는 피부, 장, 폐, 그리고 구강이 포함된다. 바이러스 군집은 일부 질병과 연관되어 있으며, 단순히 세균 군집을 반영하지 않는다.
2024년 1월, 생물학자들은 인간 미생물군유전체에서 새로운 종류의 바이로이드 유사 요소인 "오벨리스크"와 이와 관련된 단백질 그룹인 "오블린"의 발견을 보고했다.
육질충류.
여러 종의 비병원성 육질충류가 인간 위창자길에 공생하는 것으로 알려져 있는데, 여기에는 엔돌리막스 나나 ("Endolimax nana"), 엔타모에바 속의 여러 종 (특히 엔타모에바 콜라이, E. 하트만니, E. 폴레키), 그리고 요다모에바 부에츠리 종이 포함된다.
해부학적 부위.
건강한 인간 10명의 각 피부 부위 20곳에 대한 연구에서 19개 세균 문에서 205개의 식별된 속이 발견되었으며, 대부분의 염기서열은 4개 문에 할당되었다: 방선균문 (51.8%), 바실로타문 (24.4%), 프로테오박테리아 (16.5%), 박테로이데테스문 (6.3%). 건강한 인간의 피부에는 많은 곰팡이 속이 존재하며, 신체 부위에 따라 약간의 변이가 있지만, 병리학적 조건에서는 특정 속이 해당 부위에서 우세해지는 경향이 있다. 예를 들어, 아토피 피부염에서는 말라세지아가 우세하며, 비듬이 있는 두피에서는 아크레모니움이 우세하다.
피부는 병원성 미생물의 침입을 막는 장벽 역할을 한다. 인간 피부에는 피부 안이나 위에 서식하는 미생물이 포함되어 있으며, 이는 상주하거나 일시적일 수 있다. 상주 미생물 유형은 인체 피부 유형에 따라 다르다. 대부분의 미생물은 피부의 표재성 세포에 서식하거나 분비샘과 관련되는 것을 선호한다. 기름샘이나 땀샘과 같은 이러한 분비샘은 미생물에 물, 아미노산 및 지방산을 제공한다. 또한, 기름샘과 관련된 상주 세균은 종종 그람 양성이며 병원성일 수 있다.
결막.
소수의 세균과 곰팡이는 일반적으로 결막에 존재한다. 세균의 종류에는 그람 양성 구균 (예: 포도상구균과 연쇄상구균)과 그람 음성 간균 및 구균 (예: 헤모필루스와 나이세리아)이 존재한다. 곰팡이 속에는 칸디다, 아스페르길루스, 푸른곰팡이가 포함된다. 눈물샘은 지속적으로 분비하여 결막을 촉촉하게 유지하며, 간헐적인 깜박임은 결막을 윤활하고 이물질을 씻어낸다. 눈물에는 리소자임과 같은 살균제가 포함되어 있어 미생물이 리소자임을 견디고 상피 표면에 정착하기 어렵다.
위창자길.
인간의 위창자길 미생물군유전체 구성은 출생 시 확립된다. 제왕절개 또는 질식 분만 또한 장의 미생물 구성에 영향을 미친다. 질을 통해 태어난 아기는 어머니에게서 발견되는 것과 유사한 비병원성, 유익한 장 미생물군유전체를 가지고 있다. 그러나 제왕절개로 태어난 아기의 장 미생물군유전체는 대장균과 포도상구균과 같은 더 많은 병원성 세균을 보유하며, 비병원성, 유익한 장 미생물군유전체를 발달시키는 데 더 많은 시간이 필요하다.
일부 장내미생물군과 인간 사이의 관계는 단순히 편리 공생 (해를 끼치지 않는 공존)이 아니라 오히려 상리 공생 관계이다. 일부 인간 장내 미생물은 식이 섬유를 발효시켜 아세트산과 뷰티르산과 같은 짧은 사슬 지방산 (SCFA)으로 만들어 숙주에게 이롭게 하는데, 이들은 숙주에 의해 흡수된다. 장내 세균은 또한 비타민 B와 비타민 K 합성뿐만 아니라 담즙산, 스테롤, 그리고 외래 물질 대사에도 역할을 한다. 이들이 생산하는 짧은 사슬 지방산과 다른 화합물들의 전신적인 중요성은 호르몬과 같으며, 장내 미생물 자체가 내분비 기관처럼 기능하는 것으로 보인다. 그리고 장내 미생물의 조절 이상은 많은 염증성 및 자가면역 질환과 관련되어 있다.
인간 장내 미생물군유전체의 구성은 시간이 지남에 따라, 식단이 바뀜에 따라, 그리고 전반적인 건강이 변화함에 따라 변한다. 2016년 7월에 발표된 15개의 인간 무작위 대조 시험에 대한 체계적 고찰에 따르면, 비피도박테리움 및 락토바킬루스속 속 ("B. longum", "B. breve", "B. infantis", "L. helveticus", "L. rhamnosus", "L. plantarum", "L. casei")에서 유래한 특정 상업적으로 이용 가능한 프로바이오틱스 균주를 1~2개월 동안 매일 109~1010 CFU의 경구 투여량으로 복용할 때, 특정 중추신경계 질환—불안, 우울증, 자폐 스펙트럼 장애, 강박장애—에서 치료 효능(즉, 행동 결과 개선)을 보이며, 특정 기억 측면을 개선한다.
요도와 방광.
비뇨생식계에는 미생물군유전체가 있는 것으로 보인다. 이는 요로감염증 징후를 보일 때 세균뇨를 검출하기 위해 표준 임상 미생물 배양 방법을 오랫동안 사용해 왔다는 점을 고려할 때 예상치 못한 발견이며, 이러한 검사에서 세균이 존재하지 않는 것으로 나타나는 경우가 흔하다. 일반적인 미생물 배양 방법은 정상적으로 존재하는 많은 종류의 세균 및 기타 미생물을 감지하지 못하는 것으로 보인다. 2017년 현재, 염기서열 분석 방법을 사용하여 이러한 미생물을 식별하여 요로 문제와 건강한 사람 간의 미생물군유전체 차이가 있는지 여부를 확인하고 있다. 비뇨생식계와는 대조적으로 방광의 미생물군유전체를 적절히 평가하려면 소변 샘플을 방광에서 직접 채취해야 하며, 이는 종종 카테터를 사용하여 수행된다.
질 미생물군유전체는 질에 서식하는 종과 속을 의미한다. 이들 유기체는 감염으로부터 보호하고 질 건강을 유지하는 데 중요한 역할을 한다. 폐경 전 여성에게서 발견되는 가장 풍부한 질 미생물은 락토바킬루스속에서 유래하며, 이는 과산화 수소와 젖산을 생산하여 병원체를 억제한다. 세균의 종 구성과 비율은 월경 주기의 단계에 따라 달라진다. 민족성 또한 질 미생물군에 영향을 미친다. 아프리카계 미국인 여성의 경우 과산화수소를 생산하는 락토바실루스의 발생률이 낮고 질 pH가 더 높다. 성교와 항생제와 같은 다른 영향 요인들은 락토바실루스의 손실과 관련이 있다. 또한, 연구에 따르면 콘돔을 사용한 성교는 락토바실루스 수치를 실제로 변화시키고, 질 미생물군 내의 대장균 수치를 증가시키는 것으로 나타났다. 정상적이고 건강한 질 미생물군유전체의 변화는 칸디다증 또는 세균성 질염과 같은 감염의 징후이다. 칸디다 알비칸스는 락토바실루스 종의 성장을 억제하는 반면, 과산화수소를 생산하는 락토바실루스 종은 질과 장 모두에서 칸디다 알비칸스의 성장과 독성을 억제한다.
질에서 검출된 곰팡이 속에는 칸디다, 피키아, 유로티움, 알테르나리아, 로도토룰라, 클라도스포리움 등이 있다.
태반.
최근까지 태반은 무균 기관으로 간주되었으나, 태반 조직에 서식하는 공생성 비병원성 세균 종과 속이 확인되었다. 그러나 소규모 생체량 샘플은 쉽게 오염될 수 있기 때문에 "태반 미생물군유전체"의 존재는 여러 연구에서 비판받으며 논란의 여지가 있다.
최근까지 여성의 상부 생식관은 무균 환경으로 간주되었다. 다양한 미생물이 생식 연령의 건강하고 무증상 여성의 자궁에 서식한다. 자궁의 미생물군유전체는 질 및 위창자길의 미생물군유전체와 현저히 다르다.
인간의 입 안에 있는 환경은 그곳에서 발견되는 특징적인 미생물의 성장을 가능하게 한다. 물과 영양원의 공급원은 물론 적당한 온도를 제공한다. 입에 상주하는 미생물은 산에 민감한 미생물이 염산에 의해 파괴되는 입에서 위로 기계적으로 씻겨나가는 것을 막기 위해 치아와 잇몸에 달라붙는다.
구강의 혐기성 세균에는 악티노미세스, "Arachnia", 박테로이데스, 비피도박테리움, 유박테리움, 푸소박테리움, 락토바킬루스속, "Leptotrichia", "Peptococcus", "Peptostreptococcus", 프로피오니박테리움, "Selenomonas", 트레포네마, 그리고 "Veillonella"가 포함된다. 구강에서 자주 발견되는 곰팡이 속으로는 칸디다, 클라도스포리움, 아스페르길루스, 푸사리움, 글로무스, 알테르나리아, 페니실륨, 크립토코쿠스 등이 있다.
세균은 단단하고 부드러운 구강 조직 모두에 미생물막을 형성하여 구강 환경에 부착하고 번성하며 환경 요인과 항균제로부터 보호받을 수 있다. 침은 핵심적인 미생물막 항상성 역할을 하여 세균의 재정착을 통한 형성 및 미생물막 축적을 분리하여 성장을 조절한다. 또한 영양분과 온도 조절 수단을 제공한다. 미생물막의 위치에 따라 노출되는 영양분 유형이 결정된다.
구강 세균은 환경을 감지하고 숙주를 회피하거나 변형하는 메커니즘을 진화시켰다. 그러나 고도로 효율적인 선천적 숙주 방어 시스템은 끊임없이 세균의 정착을 감시하고 국소 조직의 세균 침입을 방지한다. 치태 세균과 선천적 숙주 방어 시스템 사이에는 역동적인 균형이 존재한다.
숙주 구강과 구강 미생물 간의 이러한 역동성은 몸으로 들어가는 입구를 제공하므로 건강과 질병에 중요한 역할을 한다.
건강한 균형은 상리 공생 관계를 나타내며, 여기서 구강 미생물은 병원체의 성장과 부착을 제한하는 반면 숙주는 이들이 번성할 환경을 제공한다. 면역 상태 변화, 상주 미생물 변화, 영양분 가용성 변화와 같은 생태학적 변화는 상리 관계에서 기생 관계로 전환되어 숙주가 구강 및 전신 질환에 취약하게 된다. 당뇨병 및 심혈관 질환과 같은 전신 질환은 불량한 구강 건강과 관련되어 있다. 특히 중요한 것은 두 가지 주요 치과 질환, 즉 충치와 치주염에서 구강 미생물의 역할이다. 치주 조직에 병원체가 정착하면 과도한 면역 반응이 발생하여 치아와 잇몸 사이의 공간이 깊어지는 치주낭이 생긴다. 이는 혐기성 병원균에 대한 혈액이 풍부한 보호 저장소 역할을 한다. 신체의 다양한 부위에서 발생하는 전신 질환은 구강 미생물이 치주낭과 구강 막을 우회하여 혈액으로 유입되어 발생할 수 있다.
지속적인 올바른 구강 위생은 구강 및 전신 질환 예방의 주요 방법이다. 이는 미생물막의 밀도와 잠재적 병원성 세균의 과증식을 줄여 질병을 예방한다. 그러나 구강 미생물군유전체, 유전학, 면역 반응 변화가 만성 감염 발생에 영향을 미치므로 올바른 구강 위생만으로는 충분하지 않을 수 있다. 항생제 사용은 이미 퍼진 감염을 치료할 수 있지만, 미생물막 내의 세균에는 효과적이지 않다.
건강한 비강 미생물군유전체는 코리네박테리움(Corynebacterium)과 포도상구균(Staphylococcus) 종이 우세하다. 점막 미생물군유전체는 바이러스 감염을 조절하는 데 중요한 역할을 한다.
구강과 마찬가지로 상부 및 하부 호흡기계에는 미생물을 제거하는 기계적 억제 장치가 있다. 술잔 세포는 점액을 생산하여 미생물을 가두고, 계속 움직이는 섬모 상피 세포를 통해 호흡기계 밖으로 이동시킨다. 또한, 비강 점액에는 리소자임 효소가 포함되어 살균 효과를 낸다. 상부 및 하부 호흡기계는 자체적인 미생물군을 가지고 있는 것으로 보인다. 폐 세균 미생물군유전체는 주로 9개 주요 세균 속으로 구성된다: 프레보텔라(Prevotella), 스핑고모나스(Sphingomonas), 슈도모나스(Pseudomonas), 아시네토박터(Acinetobacter), 푸소박테리움(Fusobacterium), 메가스파에라(Megasphaera), 베이요넬라(Veillonella), 포도상구균(Staphylococcus), 연쇄상구균(Streptococcus). 호흡기계의 "정상 생물상"으로 간주되는 일부 세균은 특히 면역억제 환자에게 심각한 질병을 유발할 수 있다. 여기에는 스트렙토코쿠스 피오게네스(Streptococcus pyogenes), 헤모필루스 인플루엔자(Haemophilus influenzae), 스트렙토코쿠스 뉴모니아(Streptococcus pneumoniae), 나이세리아 메닌기티디스(Neisseria meningitidis), 포도상구균 아우레우스(Staphylococcus aureus)가 포함된다. 폐 미코바이옴을 구성하는 곰팡이 속에는 칸디다(Candida), 말라세지아(Malassezia), 네오사르토리아(Neosartorya), 사카로미세스(Saccharomyces), 아스페르길루스(Aspergillus) 등이 있다.
낭포성 섬유증 환자에게서는 호흡기계의 세균 및 곰팡이 속 분포가 비정상적으로 관찰된다. 이들의 세균총은 종종 항생제 내성 및 느리게 성장하는 세균을 포함하며, 이러한 병원체의 빈도는 연령에 따라 변화한다.
쓸개길.
전통적으로 쓸개길은 무균 상태로 간주되었으며, 담즙 내 미생물의 존재는 병리학적 과정의 지표였다. 이러한 가정은 정상 담관에서 세균 균주를 분리하는 데 실패함으로써 확인되었다. 2013년부터 정상 담도 미생물군유전체가 외부 미생물에 의한 쓸개길의 집락화를 방지하는 별도의 기능적 층이라는 것을 보여주는 논문들이 나오기 시작했다.
인체는 수많은 세균 유전자에 필수 영양소의 근원을 의존한다. 군유전체학 및 역학 연구 모두 인간 미생물군유전체가 제2형 당뇨병 및 비만에서 염증성 장 질환, 파킨슨병, 심지어 우울증과 같은 정신 건강 상태에 이르기까지 광범위한 질병을 예방하는 데 중요한 역할을 한다는 것을 보여준다. 장내미생물군과 다른 세균 사이의 공생 관계는 개인의 면역 반응에 영향을 미칠 수 있다. 장내 미생물에 의해 생성되는 대사산물은 제2형 당뇨병의 원인 인자인 것으로 보인다. 비록 초기 단계이긴 하지만, 미생물군유전체 기반 치료법은 특히 약물 내성 C. 디피실 감염 치료 및 당뇨병 치료에서 유망한 것으로 나타나고 있다.
클로스트리디오이데스 디피실 감염.
세균 "C. difficile"의 압도적인 존재는 위장관 감염으로 이어진다. 이는 일반적으로 항생제 투여로 인해 발생한다고 여겨지는 미생물군유전체 이상균총과 관련이 있다. 항생제 사용은 위장관 내 유익한 장내 미생물을 박멸하여 병원성 세균이 우위를 점하는 것을 막는다. "C. difficile" 감염의 전통적인 치료법은 추가적인 항생제 요법을 포함하지만, 유효율은 평균 20~30%이다. 건강한 장내 세균의 중요성을 인식한 연구자들은 대변 미생물총 이식 (FMT)이라는 시술로 전환했다. 이 시술은 "C. difficile" 감염 (CDI)과 같은 위장 질환을 겪는 환자에게 건강한 사람의 대변 내용물을 이식하여 정상적인 장내 미생물군유전체의 기능을 회복시키려는 것이다. 대변 미생물총 이식은 항생제가 듣지 않거나 항생제 치료 후 재발하는 CDI 환자에게 약 85~90%의 효과를 보인다. 대부분의 CDI 환자는 한 번의 FMT 치료로 회복된다.
암은 일반적으로 숙주 유전학과 환경 요인의 질병이지만, 미생물은 인간 암의 약 20%에 관련되어 있다. 특히 대장암의 잠재적 요인에 관해서는, 세균 밀도가 작은창자보다 백만 배 높으며, 대장과 직장암은 작은창자암보다 약 12배 더 많이 발생하는데, 이는 미생물군유전체가 대장 및 직장암에서 병원성 역할을 할 수 있음을 시사한다. 미생물 밀도는 대장암 평가에서 예후 도구로 사용될 수 있다.
미생물군유전체는 (i) 종양 세포 증식 및 사멸의 균형 변경, (ii) 면역 체계 기능 조절, (iii) 숙주 생성 인자, 식품 및 의약품의 대사에 영향을 미침으로써 발암에 세 가지 광범위한 방식으로 영향을 미칠 수 있다. 피부, 구인두, 호흡기, 소화기 및 비뇨생식기와 같은 경계 표면에서 발생하는 종양은 미생물군유전체를 보유한다. 종양 부위에 상당한 미생물이 존재한다고 해서 연관성이나 인과 관계가 확립되는 것은 아니다. 오히려 미생물은 종양의 산소 장력 또는 영양분 프로파일을 지지하는 환경을 발견할 수 있다. 특정 미생물 개체군의 감소 또는 유도된 산화 스트레스 또한 위험을 증가시킬 수 있다. 지구상에 있는 약 1030개의 미생물 중 10개는 국제 암 연구 기관에 의해 인간 발암 물질로 지정되었다. 미생물은 숙주에서 직접 세포 증식을 유도하는 단백질 또는 다른 인자를 분비할 수 있으며, 발암에 기여하는 방식으로 급성 또는 만성 염증을 유도하는 것을 포함하여 숙주 면역 체계를 상향 조절 또는 하향 조절할 수 있다.
면역 기능과 염증 발생의 관계에 대해, 점막 장벽은 환경 위험에 노출되며 항상성을 유지하기 위해 신속하게 복구되어야 한다. 손상된 숙주 또는 미생물군유전체의 회복력 또한 악성 종양에 대한 저항력을 감소시켜 염증과 암을 유발할 수 있다. 일단 장벽이 손상되면 미생물은 다양한 경로를 통해 전염증성 또는 면역억제 프로그램을 유발할 수 있다. 예를 들어, 암 관련 미생물은 종양 미세 환경 내에서 NF-κB 신호 전달을 활성화하는 것으로 보인다. 뉴클레오타이드 결합 올리고머화 도메인 유사 수용체 (NLR) 계열 구성원인 NOD2, NLRP3, NLRP6 및 NLRP12와 같은 다른 패턴 인식 수용체는 대장암 매개에 역할을 할 수 있다. 마찬가지로 헬리코박터 파일로리(Helicobacter pylori)는 위에서 만성 염증 반응을 유도하여 위암 위험을 증가시키는 것으로 보인다.
염증성 장 질환은 궤양성 대장염과 크론병이라는 두 가지 질병으로 구성되며, 이 두 질병 모두 장내 미생물군유전체의 교란(즉, 이상증식)을 보인다. 이러한 이상증식은 장내 미생물 다양성의 감소 형태로 나타나며, 개인의 선천 면역 반응을 변화시키는 숙주 유전자의 결함과 관련이 있다.
장뇌 상호작용 장애.
과민 대장 증후군 및 복부 팽만과 같은 다른 기능성 위장 장애 환자에서 특정 세균 그룹의 풍부도 변화가 관찰되었다. 특히, 비피도박테리움 및 락토바킬루스속과 같은 유익한 세균의 감소; 박테로이데스 및 프로테오박테리아와 같은 잠재적으로 해로운 세균의 증가. 이러한 미생물 변화는 장 투과성 증가 ("새는 장"), 내장 과민성 (자극에 대한 장의 민감도 증가), 장 운동성 변화, 면역 체계 활성화에 기여할 수 있다.
인간면역결핍 바이러스.
HIV 질병 진행은 장 미생물군유전체의 구성과 기능에 영향을 미치며, HIV 음성, HIV 양성, 그리고 ART 후 HIV 양성 개체군 사이에 주목할 만한 차이가 있다. HIV는 밀착연접에 영향을 미쳐 장 상피 장벽 기능의 무결성을 감소시킨다. 이러한 손상은 장 상피를 통한 전위(translocation)를 허용하며, 이는 HIV 감염자에게서 관찰되는 염증 증가에 기여하는 것으로 생각된다.
질 미생물군유전체는 HIV 감염성에 영향을 미치며, 여성이 세균성 질염, 즉 질 세균의 비정상적인 균형을 특징으로 하는 상태일 때 감염 및 전파 위험이 증가한다. 전염증성 사이토카인과 질 내 CCR5+ CD4+ 세포의 증가와 함께 감염성 증가가 관찰된다. 그러나 질 내 락토바실루스 수치가 증가하면 감염성 감소가 나타나는데, 이는 항염증 상태를 촉진한다.
백세인의 장 미생물군유전체.
100세 이상인 백세인은 독특한 장 미생물군유전체를 가지고 있다. 이 미생물군유전체는 새로운 2차 담즙산을 합성할 수 있는 미생물이 특징적으로 풍부하다. 이러한 2차 담즙산에는 건강한 노화에 기여할 수 있는 다양한 리토콜산 이성질체가 포함된다.
사망과 함께 살아있는 몸의 미생물군유전체는 붕괴되고, 괴사체 미생물군유전체라고 불리는 다른 구성의 미생물이 복잡한 물리적 분해 과정의 중요한 활성 구성원으로 자리 잡는다. 시간 경과에 따른 예측 가능한 변화는 사망 시간을 결정하는 데 유용할 것으로 생각된다.
2009년 연구에서는 인간의 개입으로 인한 생물상 (미소동물상 포함)의 감소가 인간 건강, 병원 안전 절차, 식품 제품 설계 및 질병 치료를 방해할 수 있는지에 대해 의문을 제기했다.
변화, 조절 및 전달.
위생, 프로바이오틱스,&lt;ref name="10.1038/s41385-022-00564-1"&gt;&lt;/ref&gt; 프리바이오틱스, 공생생물, 광선 치료, 미생물군유전체 이식 (대변 미생물총 이식 또는 피부), 항생제, 운동, 식단, 모유 수유, 노화는 피부와 장과 같은 다양한 해부학적 시스템 또는 지역에서 인간 미생물군유전체를 변화시킬 수 있다.
사람 간 전파.
인간 미생물군유전체는 어머니와 그 자녀 사이, 그리고 같은 세대에 사는 사람들 사이에서 전파된다.
원초적 연구에 따르면 태국 이민자들이 미국에 정착했거나 라틴 아메리카인들이 미국으로 이민 왔을 때와 같이 한 나라에서 다른 나라로 이주할 경우 미생물군유전체에 즉각적인 변화가 발생할 수 있음을 시사한다. 미생물군유전체 다양성 손실은 비만 개인 및 이민자의 자녀에게서 더 컸다.
셀룰로스 소화.
2024년 연구에 따르면 셀룰로스를 소화할 수 있는 장내미생물군이 인간 미생물군유전체에서 발견될 수 있으며, 산업사회에 사는 사람들에게서 그 수가 더 적다는 것을 시사한다.
섹솜.
섹솜(Sexome)은 삽입 성교 후 생식기에 남겨진 미생물을 의미한다. 법과학의 맥락에서 섹솜은 남성의 DNA가 없는 경우 성폭행 사건의 가해자 식별에 잠재적으로 도움이 될 수 있다.
푸로마이신()은 번역 과정에서 폴리펩타이드 사슬 합성을 조기에 종결시키는 단백질 합성 저해 항생제이다.
번역의 저해.
푸로마이신은 세균인 스트렙토미세스 알보니게르("Streptomyces alboniger")로부터 유래한 아미노뉴클레오사이드 항생제로 리보솜에서 일어나는 번역 과정에서 조기 사슬 종결을 유발한다. 분자의 일부는 아미노아실화된 tRNA의 3' 말단과 유사하다. 푸로마이신은 A 부위에 들어가서 성장하는 사슬로 이동하여 푸로마이실화된 신생 사슬이 형성되고 사슬이 조기에 방출된다. 현재 정확한 작용 메커니즘은 알려져 있지 않지만, 3' 위치에는 tRNA의 정상적인 에스터 결합 대신 아마이드 결합이 포함되어 있다. 이로 인해 분자는 가수분해에 대한 저항력이 훨씬 커지고 리보솜이 정지한다.
푸로마이신은 원핵생물이나 진핵생물 모두에 대해 선택적이다.
또한 주목할 점은 푸로마이신은 mRNA 디스플레이에 중요하다는 것이다. 이 반응에서 푸로마이신 분자는 mRNA 주형의 끝에 화학적으로 부착되고, 이후 단백질로 번역된다. 그러면 푸로마이신은 성장하는 펩타이드 사슬에 공유 결합을 형성하여 mRNA가 번역 산물에 물리적으로 결합될 수 있다.
푸로마이실화된 신생 사슬을 인식하는 항체는 새로 합성된 폴리펩타이드를 정제하고 면역형광법을 통해 활발하게 번역되는 리보솜의 분포를 시각화하는 데에도 사용될 수 있다.
펩티데이스 저해제.
푸로마이신은 다이펩티딜펩티데이스 II(세린 펩티데이스)와 세포질 알라닐 아미노펩티데이스(메탈로펩티데이스)의 가역적 저해제이다. 저해 메커니즘은 잘 이해되지 않지만, 푸로마이신을 사용하면 아미노펩티데이스 M(활성)과 세포질 알라닐 아미노펩티데이스(푸로마이신에 의해 저해됨)를 구별할 수 있다.
푸로마이신은 세포 배양 시스템에서 선택적 제제로 세포생물학에서 사용된다. 푸로마이신은 원핵세포와 진핵세포에 독성이 있다. 푸로마이신에 대한 내성은 스트렙토미세스 생산 균주에서 발견된 푸로마이신 "N"-아세틸기전이효소(PAC)를 암호화하는 pac 유전자에 의해 부여된다. 푸로마이신은 물에 녹으며(50mg/mL), 10mg/mL에서 무색 용액이다. 푸로마이신은 -20 °C에서 보관할 경우 용액 상태로 1년 동안 안정적이다. 세포 배양에서 선택제로서 권장되는 복용량은 1~10 μg/mL 범위이지만, 농도가 1 μg/mL만큼 낮아도 진핵세포에 독성을 나타낼 수 있다. 푸로마이신은 빠르게 작용하여 내성이 없는 세포의 99% 이상을 하루 안에 죽일 수 있다.
대장균의 선택.
푸로마이신은 대장균에 대한 활성이 약하다. 푸로마이신 내성 형질전환체는 푸로마이신 125 μg/mL이 보충된 LB 아가 배지에서 선별된다. 하지만 대장균을 선택하기 위해 푸로마이신을 사용하려면 정확한 pH 조절이 필요하며, 어떤 균주를 선택하느냐에 따라 달라진다. 번거로움 없는 선택과 최적의 결과를 위해 특별히 변형된 푸로마이신을 사용하는 것이 가능하다. 푸로마이신을 함유한 플레이트는 4 °C에서 보관할 경우 1개월 동안 안정적이다.
효모의 선택.
효모의 푸로마이신 내성은 푸로마이신 "N"-아세틸기전이효소(pac) 유전자의 발현을 통해서도 부여될 수 있다. 푸로마이신의 치사 농도는 포유류 세포주보다 사카로미세스 세레비시아("Saccharomyces cerevisiae") 균주에서 훨씬 더 높다. 다제내성 유출 펌프 Pdr5를 암호화하는 유전자가 결실되면 세포가 푸로마이신에 민감해진다.
쥐에서의 기억 상실.
기억 과정에 필요한 장기적인 시냅스 가소성은 단백질 수준에서 형태학적 변화를 필요로 한다. 푸로마이신은 진핵세포에서 단백질 합성을 저해하기 때문에 연구자들은 이 약물을 주사하면 쥐에게 단기 기억 상실과 장기 기억 상실이 모두 발생한다는 것을 보여줄 수 있었다.
누르마호메드 마호메도비치 누르마호메도우(, , 1970년 9월 2일~)는 러시아 태생 우크라이나의 전직 삼보 선수이다.
1992년 세계 삼보 선수권 대회 금메달, 1992년 유럽 삼보 선수권 대회 금메달, 1993년 유럽 삼보 선수권 대회 은메달을 획득했으며 아브둘마나프 누르마고메도프의 동생, 하비프 누르마고메도프의 삼촌이다.
1970년 소련 다게스탄 자치 소비에트 사회주의 공화국에서 태어나 어린 시절 프리스타일 레슬링에 입문했다. 1983년 공부를 위해 우크라이나 소비에트 사회주의 공화국 폴타바로 이주해 삼보와 유도를 배웠고 1993년 폴타바 경제 교역 대학교를 졸업했다.
누르마호메도우는 국제 대회에서 우크라이나를 대표했고 1992년 세계 삼보 선수권 대회 82kg 이하에서 금메달을, 1992년 삼보 월드컵 단체전에서 금메달을 획득했다. 또한 1992년 유럽 삼보 선수권 대회 82kg 이하에서 금메달을, 1993년 유럽 삼보 선수권 대회 82kg 이하에서 은메달을 획득했다.
컴퓨팅에서 라스베이거스 알고리즘(Las Vegas algorithm)은 항상 올바른 결과를 제공하는 확률적 알고리즘이다. 즉, 항상 올바른 결과를 생성하거나 실패를 알린다. 그러나 라스베이거스 알고리즘의 실행 시간은 입력에 따라 달라진다. 라스베이거스 알고리즘의 일반적인 정의에는 알고리즘에서 사용되는 임의 정보 또는 엔트로피 공간에 대해 기대값이 수행되는 기대 실행 시간이 유한하다는 제약이 포함된다. 대안적인 정의는 라스베이거스 알고리즘이 항상 종료되지만 (유효하지만) 해결책을 찾지 못했음을 나타내기 위해 솔루션 공간의 일부가 아닌 기호를 출력할 수 있다고 요구한다. 라스베이거스 알고리즘의 본질은 가능한 솔루션의 수가 제한적이고, 후보 솔루션의 정확성을 검증하는 것이 비교적 쉽지만 솔루션을 찾는 것이 복잡한 상황에 적합하다.
명제 만족도(SAT)에 대한 데이비스-푸트넘 알고리즘의 일부 변형과 같이 계산적으로 어려운 문제에 대한 체계적인 검색 방법도 비결정적 결정을 활용하므로 라스베이거스 알고리즘으로 간주될 수 있다.
라스베이거스 알고리즘은 1979년 라스즐로 바바비에 의해 그래프 동형 문제의 맥락에서 몬테카를로 알고리즘의 듀얼로 소개되었다. 바바비는 동전 던지기 예시와 함께 "라스베이거스 알고리즘"이라는 용어를 도입했다. 이 알고리즘은 일련의 독립적인 동전 던지기에 의존하며, 실패(결과 없음)의 작은 확률이 있다. 그러나 몬테카를로 알고리즘과 대조적으로 라스베이거스 알고리즘은 보고된 모든 결과의 정확성을 보장할 수 있다.
// 라스베이거스 알고리즘, A는 길이가 n인 배열이라고 가정한다.
// 목표: A[k] == 1이 되도록 올바른 인덱스 k를 반환한다.
n = A.length
repeat:
k = RandInt(n)
if A[k] == 1,
위에서 언급했듯이 라스베이거스 알고리즘은 항상 올바른 결과를 반환한다. 위 코드는 이 속성을 보여준다. 목표는 배열 A에서 값 1을 포함하는 인덱스를 찾는 것이다. 변수 k는 무작위로 생성된다. k가 생성된 후 k는 배열 A의 인덱스로 사용된다. 이 인덱스가 값 1을 포함하면 k가 반환되고, 그렇지 않으면 알고리즘은 1을 찾을 때까지 이 과정을 반복한다. 이 라스베이거스 알고리즘은 올바른 답을 찾는 것이 보장되지만, 고정된 실행 시간을 가지지 않는다. 무작위화(위 코드의 4행)로 인해 알고리즘이 종료되기 전까지 임의로 많은 시간이 경과할 수 있다.
이 섹션에서는 알고리즘이 라스베이거스 유형이 되기 위한 조건을 제공한다.
알고리즘 A는 문제 클래스 X에 대한 라스베이거스 알고리즘이다, 만약
라스베이거스 알고리즘에는 세 가지 완전성 개념이 있다.
P(RTA,x ≤ t)가 A가 시간 t 내에 풀 수 있는 인스턴스 x에 대한 솔루션을 찾을 확률을 나타낸다고 하자. 그러면 A는 각 x에 대해 다음을 만족하는 경우에만 완전하다.
P(RTA,x ≤ tmax) = 1인 t가 존재한다.
대략적인 완전성은 주로 이론적인 관심사이다. 왜냐하면 솔루션을 찾는 시간 제한은 보통 너무 커서 실제 사용에 거의 유용하지 않기 때문이다.
응용 시나리오.
라스베이거스 알고리즘은 문제 설정에 따라 평가 기준이 다르다. 라스베이거스 알고리즘은 정해진 시간 복잡도가 없으므로 이러한 기준은 서로 다른 시간 제한을 가진 세 가지 범주로 나뉜다. 몇 가지 가능한 응용 시나리오는 다음과 같다.
시간 제한이 없는 유형 1의 경우, 평균 실행 시간이 실행 시간 동작을 나타낼 수 있다. 유형 2의 경우와는 다르다.
여기서 P(RT ≤ tmax), 즉 시간 내에 해결책을 찾을 확률이 실행 시간 동작을 설명한다.
유형 3의 경우, 실행 시간 동작은 rtd(t) = P(RT ≤ t)로 정의되는 실행 시간 분포 함수 rtd: R → [0,1] 또는 그 근사치로만 나타낼 수 있다.
실행 시간 분포(RTD)는 라스베이거스 알고리즘의 실행 시간 동작을 설명하는 독특한 방법이다.
이 데이터를 통해 평균 실행 시간, 표준 편차, 중앙값, 백분위수 또는 임의의 시간 제한 t에 대한 성공 확률 P(RT ≤ t)와 같은 다른 기준을 쉽게 얻을 수 있다.
라스베이거스 알고리즘은 탐색 문제에서 자주 발생한다. 예를 들어, 온라인에서 정보를 찾는 사람은 원하는 정보를 얻기 위해 관련 웹사이트를 검색할 수 있다. 따라서 시간 복잡도는 "운이 좋아" 즉시 콘텐츠를 찾는 것부터 "운이 없어" 많은 시간을 소비하는 것까지 다양하다. 올바른 웹사이트를 찾으면 오류가 발생할 가능성은 없다.
확률적 퀵 정렬.
# A는 n개의 요소를 가진 배열이다.
def randomized_quicksort(A):
return A # A는 정렬되어 있다.
i = random.randrange(1, n) # 1~n 범위에서 무작위 숫자를 선택한다.
X = A[i] # 피벗 요소이다.
"""위 그림과 같이 A를 x보다 작은 요소, x, x보다 큰 요소로 분할한다.
A[1 to i-1]과 A[i+1 to n]에 대해 퀵 정렬을 실행한다.
정렬된 배열을 얻기 위해 응답을 결합한다."""
간단한 예로는 확률적 퀵 정렬이 있다. 여기서 피벗은 무작위로 선택되며, 요소를 피벗보다 작은 요소, 피벗과 같은 요소, 피벗보다 큰 요소의 세 부분으로 나눈다. 퀵 정렬은 항상 이 경우 정렬된 배열인 해결책을 생성한다. 불행히도 시간 복잡도는 그렇게 분명하지 않다. 실행 시간은 어떤 요소를 피벗으로 선택하는지에 따라 달라진다.
퀵 정렬의 실행 시간은 피벗이 얼마나 잘 선택되는지에 크게 의존한다. 피벗 값이 너무 크거나 작으면 분할이 불균형하여 효율성이 떨어진다. 그러나 피벗 값이 배열의 중간에 가까우면 분할이 상당히 균형을 이루어 더 빠른 실행 시간을 제공한다. 피벗이 무작위로 선택되므로 실행 시간은 대부분의 경우 좋고 때때로 나쁘다.
평균적인 경우, 분석이 입력 분포에 의존하는 것이 아니라 알고리즘이 내리는 무작위 선택에 의존하므로 결정하기 어렵다. 퀵 정렬의 평균은 알고리즘이 피벗을 선택할 때 내릴 수 있는 모든 가능한 무작위 선택에 대해 계산된다.
최악의 실행 시간은 Θ(n2)이지만, 평균 실행 시간은 Θ(nlogn)이다. 최악의 경우는 자주 발생하지 않는 것으로 밝혀졌다. n 값이 클수록 실행 시간은 높은 확률로 Θ(nlogn)이다.
피벗이 매번 중간 값 요소일 확률은 n개의 숫자 중 하나이므로 매우 드물다. 그러나 분할이 50%-50% 대신 10%-90%인 경우에도 재귀 트리의 깊이가 여전히 O(logn)이고 각 재귀 수준에서 O(n) 시간이 소요되므로 실행 시간은 동일하다.
8퀸 문제에 대한 확률적 그리디 알고리즘.
8퀸 문제는 일반적으로 퇴각검색 알고리즘으로 해결된다. 그러나 라스베이거스 알고리즘을 적용할 수 있으며, 사실 퇴각검색보다 더 효율적이다.
체스판에 8개의 퀸을 서로 공격하지 않도록 놓는다. 퀸은 같은 행, 열, 대각선에 있는 다른 말들을 공격한다는 것을 기억하자.
k개의 행, 0 ≤ k ≤ 8이 퀸으로 성공적으로 채워졌다고 가정한다.
k = 8이면 성공적으로 중지한다. 그렇지 않으면 k + 1행을 채우는 작업을 계속한다.
기존 퀸에 의해 공격받지 않는 이 행의 모든 위치를 계산한다. 그러한 위치가 없으면 실패한다. 그렇지 않으면 하나를 무작위로 선택하고, k를 증가시킨 후 반복한다.
퀸을 놓을 수 없으면 알고리즘은 단순히 실패한다는 점에 유의한다. 그러나 이 과정은 반복될 수 있으며 매번 다른 배열을 생성할 것이다.
기댓값 다항식 실행 시간을 가진 라스베이거스 알고리즘을 가진 결정 문제의 복잡도 종류는 ZPP이다.
다음과 같이 밝혀졌다.
이는 라스베이거스 알고리즘이 때때로 구성되는 방식과 밀접하게 연결되어 있다. 즉, RP 클래스는 올바른 답이 "아니오"일 때 항상 올바르게 답하지만, 답이 "예"일 때 1에서 벗어난 특정 확률로 틀릴 수 있는 확률적 다항 시간 알고리즘이 존재하는 모든 결정 문제로 구성된다. 문제와 그 보수(답이 "예"와 "아니오"로 바뀌는) 모두에 대해 그러한 알고리즘이 존재할 때, 두 알고리즘을 동시에 반복적으로 실행할 수 있다. 즉, 각각의 알고리즘을 일정한 수의 단계 동안 교대로 실행하여 하나가 명확한 답을 반환할 때까지 진행한다. 이것이 기대 다항 시간으로 실행되는 라스베이거스 알고리즘을 구성하는 표준적인 방법이다. 일반적으로 라스베이거스 알고리즘의 실행 시간에는 최악의 경우 상한이 없다는 점에 유의한다.
최적의 라스베이거스 알고리즘.
라스베이거스 알고리즘을 최적으로 만들기 위해서는 예상 실행 시간을 최소화해야 한다. 이는 다음을 통해 수행할 수 있다.
최적 전략의 존재는 매력적인 이론적 관찰일 수 있다. 그러나 TA(x) 분포에 대한 정보를 찾는 것이 쉽지 않기 때문에 실제 생활에서는 실용적이지 않다. 더욱이 대부분의 경우 x에 대한 답이 한 번만 필요하므로 분포에 대한 정보를 얻기 위해 실험을 반복적으로 실행할 필요가 없다.
몬테카를로 알고리즘과의 관계.
라스베이거스 알고리즘은 사용되는 자원은 제한되지만 답변이 특정(일반적으로 작은) 확률로 틀릴 수 있는 몬테카를로 알고리즘과 대조된다. 라스베이거스 알고리즘은 정해진 시간 동안 실행하고 종료되지 않으면 무작위 답변을 생성함으로써 몬테카를로 알고리즘으로 변환할 수 있다. 마르코프 부등식을 적용하여 라스베이거스 알고리즘이 고정된 한계를 초과할 확률에 대한 상한을 설정할 수 있다.
다음은 라스베이거스 알고리즘과 몬테카를로 알고리즘을 비교한 표이다.
정확성 테스트를 위한 결정론적인 방법이 있다면 몬테카를로 알고리즘을 라스베이거스 알고리즘으로 바꿀 수 있다. 하지만 알고리즘을 테스트할 방법이 없다면 몬테카를로 알고리즘을 라스베이거스 알고리즘으로 바꾸기 어렵다. 반면에 라스베이거스 알고리즘을 몬테카를로 알고리즘으로 바꾸는 것은 쉽다. 이는 신뢰도 매개변수로 주어진 특정 시간 동안 라스베이거스 알고리즘을 실행함으로써 가능하다. 알고리즘이 시간 내에 해를 찾으면 성공이고, 그렇지 않으면 "죄송합니다"라고 출력할 수 있다.
다음은 비교를 위한 라스베이거스 및 몬테카를로 알고리즘의 예시이다.
짝수 n 길이를 가진 배열이 있다고 가정하자. 배열의 절반은 0이고 나머지 절반은 1이다. 여기서 목표는 1을 포함하는 인덱스를 찾는 것이다.
// A는 길이가 n인 배열이다.
// 라스베이거스 알고리즘
k = RandInt(n);
// 몬테카를로 알고리즘
repeat 300 times:
return "Failed";
라스베이거스 알고리즘은 배열에서 1을 찾을 때까지 끝나지 않으므로, 정확성을 놓고 도박을 하는 것이 아니라 실행 시간을 놓고 도박을 한다. 반면에 몬테카를로 알고리즘은 300번 실행되므로 코드를 실제로 실행하기 전까지는 300번의 루프 내에서 배열에서 "1"을 찾을지 알 수 없다. 해를 찾을 수도 있고 찾지 못할 수도 있다. 따라서 라스베이거스 알고리즘과 달리 몬테카를로 알고리즘은 실행 시간이 아니라 정확성을 놓고 도박을 한다.
최적화 이론에서 최대 유량 문제(maximum flow problem)는 최대 가능한 유량을 얻는 네트워크 흐름을 통한 실행 가능한 흐름을 찾는 것을 포함한다.
최대 유량 문제는 순환 문제와 같은 더 복잡계 네트워크 흐름 문제의 특별한 경우로 볼 수 있다. s-t 흐름(즉, 소스 s에서 싱크 t로의 흐름)의 최대값은 최대 유량 최소 컷 정리에 명시된 바와 같이 네트워크에서 s-t 컷 (즉, s를 t에서 분리하는 컷)의 최소 용량과 같다.
최대 유량 문제는 1954년 T. E. 해리스와 F. S. 로스에 의해 소련 철도 교통 흐름의 단순화된 모델로 처음 공식화되었다.