시퀀스 그래프

비교 유전체학에서 선형 그래프, 중단점 그래프 또는 인접 그래프라고도 하는 시퀀스 그래프는 정점이 DNA의 세그먼트를 나타내고 가장자리는 게놈의 세그먼트 사이의 인접성을 나타내는 양방향 그래프다.^[1]세그먼트는 나타내는 DNA 문자열로 라벨이 표시되며, 각 가장자리는 한 세그먼트의 꼬리 끝과 다른 세그먼트의 머리 끝을 연결한다.각각의 인접 가장자리는 DNA의 (비었을 가능성이 있는) 끈으로 표시된다.세그먼트의 연결된 구성 요소와 인접 에지(스레드라고 함)를 통과하면 시퀀스가 생성되는데, 일반적으로 게놈 또는 게놈의 한 단면을 나타낸다.세그먼트는 가장자리로 특정 게놈에서 이러한 블록을 배열하는 방법을 지시하는 동기화 블록으로 생각할 수 있으며, 인접 가장자리의 라벨링은 동기화 블록에 포함되지 않은 베이스를 나타낸다.null

적용들

다중 시퀀스 정렬

시퀀스 그래프는 세그먼트 사이의 동질학을 나타내는 새로운 종류의 가장자리가 추가되면서 다중 시퀀스 선형을 나타내기 위해 사용될 수 있다.^[2]게놈 집합의 경우, 각 게놈에 대해 실이 있는 Acyclic breakpoint 그래프를 만들 수 있다.${\$displaystyle a}, ${\displaystyle }$ ${\$$displaystyle$a$$$},$ ${\displaystyle \{\backslash }$$displaystyle$ b$\},$ c ${\displaystyle c}$및 $d{\displaystyle }$ ${\$$displaystyle$ $d}$ 두 세그먼트의 끝점을 $나타내는{\displaystyle }$$$ 두 $세그먼트{\displaystyle }$${\displaystyle (,}$ b${\displaystyle }$) ${\displaystystyle a}$ 및 ($c,$ d$)$에 대해 호몰로지 가장자리를$$ 생성할 수 있다$.$플레이 $스타일 c}$과 $b{\displaystyle }$ ${\displaystyle b}$에서 d ${\displaystyle$ $d$$}$까지 또는$$ ${\displaystyle d}$에서 c ${\displaystyle b}$에서 $c{\displaystyle }$ ${\displaystyle c}$까지 - 동질학의 두 가지 가능한 방향을 나타낸다.$$이러한 방식으로 다중 시퀀스 정렬을 나타내는 이점은 행렬 표현에서 허용되지 않는 반전 및 기타 구조 재배열을 포함할 수 있다는 것이다.null

변동을 나타냄

시퀀스 그래프에서 스레드를 통과할 때 가능한 경로가 여러 개일 경우 동일한 스레드로 여러 시퀀스를 나타낼 수 있다.이것은 각 게놈들이 그래프를 통과하는 한 경로에 해당하는, 약간 다른 게놈을 가진 개인의 집단을 나타내는 시퀀스 그래프를 만들 수 있다는 것을 의미한다.이 그래프들은 참조 인간 게놈의 대체물로 제안되었다.^[3]null

참조