트리플렛에서 레벨-2 계통 발생 네트워크 구성하기

Jansson과 Sung은 밀집된 입력 트리플렛 집합 T(분류군의 트리플렛 간의 지역 진화 관계에 대한 가설을 나타내는)를 주어지면, T와 일치하는 레벨-1 네트워크가 존재하는지 여부를 다항 시간 내에 결정할 수 있으며, 가능하다면 그러한 네트워크를 구성할 수 있음을 보였습니다. 여기에서 우리는 이 문제를 레벨-2 네트워크 구성의 경우에도 다항 시간 내에 해결 가능하다는 것을 보여 주어 이 작업을 확장합니다. 이는 밀도를 가정할 경우 트리플렛으로부터 신뢰할 수 있는 진화 역사들을 구성하는 것이 가능하다는 것을 보여줍니다. 이는 이러한 역사들이 비나무 모양인 경우에도 마찬가지입니다. 이는 또한 계통 발생 네트워크 구성에서 트리플렛 기반 방법의 사용에 대한 주장을 더욱 강화합니다. 우리는 또한 알고리즘을 구현하고 효모 데이터에 적용했습니다.